A permutation is an ordered arrangement of objects. For example,
2013 is one possible permutation of the digits 0, 1, 2 and 3.
If all of the permutations are listed numerically,we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
Our problem is to find the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
becoz we have 10 digits here, there is 3,628,800 (10!) possibilities to arrange these numbers in numerical order starting from
0123456789,
0123456798,
0123456879,
0123456897,
0123456978
.
.
.
.
9876543120
9876543201
9876543210
The algorithm implemented below is a single recursive function with nested_recursion and a support Boolean function shld_continue. The steps are below
1. Initiate m[10] as the loop variable for each level, n to keep track of the number of values found (remember we are looking for the 1,000,000 th lexicographic permutation) and set the level as 0 and the number of values as 10 and call the recursive function nested_recursion(m,&n,0,10)
2. For loop is initiated (and will be initiated for all the levels) and call shld_continue. This Boolean function shld_continue is a simple function to find whether the loop variable is unique or not. Remember in lexicographic permutation all the numbers are unique.
3. If shld_continue is false (that means the loop variable is unique) we move on to new if statement to check the level of the loop.
4. If the level of the loop is the lowest then we have formed the permutation otherwise we have to move into new level and proceed with the recursion.
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/*LEXICOGRAPHIC PERMUTATIONA 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 210What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?*/// The answer is 2783915460bool shld_continue(int *i,int level);void nested_recursion(int *i,int *n,int level,int limit);int main(){ // 10 Factorial = 36,28,800 int m[10]; int n =1; nested_recursion(m,&n,0,10); return 0;}void nested_recursion(int *i,int *n,int level,int limit){ for((*(i+level))=0;(*(i+level))<limit;(*(i+level))++) { if(shld_continue(i,level) == false) // This routine to avoid repeatation of the loop value { if(level==(limit-1)) // we have reached the lowest level -> so print the results { int m; if ((*n)==1000000) { printf("%d\t",(*n)); for(m=0;m<limit;m++) printf("%d ",i[m]); printf("\n"); } (*n)=(*n)+1; } else // Lowest level hasn't reached -> so continue recursion { int pass_level = level; // declared new variable to pass to the next recursion pass_level++; nested_recursion(i,n,pass_level,limit); } } }}bool shld_continue(int *i,int level){ //(*(i+level)) has the loop variable of at the level int k; bool return_continue = false; for(k=0;k<level;k++) { if((*(i+k)) == (*(i+level))) { return_continue = true; break; } } return return_continue;}The millionth lexicographic permutation is
1000000 =====>> 2 7 8 3 9 1 5 4 6 0
2 millionth lexicographic permutation is
2000000 =====>> 5 4 6 8 7 3 1 0 9 2
and the 3 millionth lexicographic permutation is
3000000 =====>> 8 2 4 1 6 9 7 5 3 0