Problem 24
Statement
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?
Solution
The code, in C.
#include <stdio.h>
void lex(int max, int a[], int s, int e, int *n, int c[], int r[])
{
int i,j,k=1,p,tmp,b[e];
if(s>e) return;
for(i=s;i<e;i++)
if(a[i]!=c[i]){
k=0;
break;
}
if(k){
(*n)++;
if(*n==max)
for(i=0;i<10;i++)
r[i]=a[i];
}
lex(max,a,s+1,e,n,c,r);
for(i=s;i<e;i++){
for(j=0;j<e;j++)
b[j]=a[j];
tmp=b[i];
for(j=i;j>=s;j--)
b[j]=b[j-1];
b[s-1]=tmp;
lex(max,b,s+1,e,n,c,r);
}
return;
}
int main(void)
{
int i,m=0,*n=&m,c[10],r[10],a[10]={0,1,2,3,4,5,6,7,8,9};
lex(1000000,a,1,10,n,c,r);
for(i=0;i<10;i++)
printf("%d",r[i]);
printf("\n");
return 0;
}
Answer
2783915460
SPEAK / ADD YOUR COMMENT
Comments are moderated.
Posts