Python,C,C++ and JAVA programs for CBSE, ISC, B.Tech and I.T Computer Science and MCA students

The Programming Project: Permutation in Lexicographical Order

Friday, September 20, 2013

Permutation in Lexicographical Order

This C program prints the permutation of n distinct objects (0 < n <= 26 )  in Lexicographical Order.



#include<stdio.h>
#include<malloc.h>
void sort(char *permutation,int n,int pos);
void replace_min (char *permutation,int n,int pos);
int main()
{
char alpha[]={'A','B','C','D','E','F','G','H','I','J','K','L','M',
          'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int n,i,flag=1,pos;
long int tot=0;
char *permutation;
printf("\n Enter the numbr of objects (max values is 26):");
scanf("%d",&n);
permutation =(char *)malloc(n*sizeof(char));
for(i=0;i<n;i++)
    permutation[i]=alpha[i];
printf("\n The permutations are:\n");
printf("\t\t      ");
for(i=0;i<n;i++)
    printf("%c",permutation[i]);
    tot=1;
while(flag)
    {
    pos=-1;
    for(i=n-1;i>=1;i--)
        {
        if(permutation[i-1]<permutation[i])
             {
             pos=i-1;
             flag=1;
             break;
             }
        }
        if(pos==-1)
            {
            flag=0;
            break;
            }
    replace_min(permutation,n,pos);
    sort(permutation,n,pos);
   printf("\n");
    printf("\t\t      ");
    for(i=0;i<n;i++)
        printf("%c",permutation[i]);
    //tot++;
    //getche();
    }
//printf("\n Total number of permutation is: %ld",tot);
return 0;
}
void sort(char *permutation,int n,int pos)
{
    int i,j;
   char temp='A';
    for(i=pos+1;i<n-1;i++)
        {
        for(j=pos+1;j<n-1;j++)
            {
            if(permutation[j]>permutation[j+1])
                {
                temp=permutation[j+1];
                permutation[j+1]=permutation[j];
                permutation[j]=temp;
                }
            }
        }
  return;
}
void replace_min(char *permutation,int n,int pos)
{
  char min='Z',temp;
  int k,min_pos=0;
  for(k=pos+1;k<n;k++)
    {
        if(permutation[k]>permutation[pos])
            {
            if(permutation[k]<min)
                {
                min=permutation[k];
                min_pos=k;
                }
            }
    }
    temp=permutation[min_pos];
    permutation[min_pos]=permutation[pos];
    permutation[pos]=temp;
    return;
}

No comments:

Post a Comment