Lexicographic permutations:Problem 24

Lexicographic permutations:Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Problem Source Euler Project

C Code

#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[]={'0','1','2','3','4','5','6','7','8','9','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++;
    printf(">>>>>>>>>>%ld",tot);
    if (tot==1000000)
        break;
    }
//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;
}