Find the lexicographic order of an integer section

Question

For the permutations given by N and k , I have a function that finds the k permutation of N in lexicographic order. Also, with perm permutation, I have a function that finds the lexicographic permutation index among all permutations of N For this, I used "factorial decomposition" as suggested in this answer .

Now I want to do the same for whole sections of N For example, for N=7 I want to be able to move between the index (left) and the section (right):

  0 ( 7 ) 1 ( 6 1 ) 2 ( 5 2 ) 3 ( 5 1 1 ) 4 ( 4 3 ) 5 ( 4 2 1 ) 6 ( 4 1 1 1 ) 7 ( 3 3 1 ) 8 ( 3 2 2 ) 9 ( 3 2 1 1 ) 10 ( 3 1 1 1 1 ) 11 ( 2 2 2 1 ) 12 ( 2 2 1 1 1 ) 13 ( 2 1 1 1 1 1 ) 14 ( 1 1 1 1 1 1 1 ) 

I have tried several things. The best I came up with was

 sum = 0; for (int i=0; i<length; ++i) sum += part[i]*i; return sum; 

which gives the following:

  0 0( 7 ) 1 1( 6 1 ) 2 2( 5 2 ) 3 3( 5 1 1 ) 3 4( 4 3 ) 4 5( 4 2 1 ) 6 6( 4 1 1 1 ) 5 7( 3 3 1 ) 6 8( 3 2 2 ) 7 9( 3 2 1 1 ) 10 10( 3 1 1 1 1 ) 9 11( 2 2 2 1 ) 11 12( 2 2 1 1 1 ) 15 13( 2 1 1 1 1 1 ) 21 14( 1 1 1 1 1 1 1 ) 

This doesn't quite work, but it seems to be on the right track. I came up with this because it calculates how many times I need to move the number down (for example, 6,3,2 goes to 6,3,1,1 ). I can’t figure out how to fix this, because I don’t know how to take into account when things need to be recombined (for example, 6,3,1,1 goes into 6,2,2 ).

Answer 1

Think about why factorial decomposition works for permutations, and the same logic works here. However, instead of using k! for the number of permutations of the objects k you must use the partition function p(n,k) for the number of partitions n with the largest part no more than k . For n=7 these numbers are:

 k | p(7,k) 0 | 0 1 | 1 2 | 4 3 | 8 4 | 11 5 | 13 6 | 14 7 | 15 

To get the lexicographic index (3,2,1,1) , for example, you calculate

 p(3+2+1+1) - [ p(3+2+1+1,3-1) + p(2+1+1,2-1) + p(1+1,1-1) + p(1,1-1) ] - 1 

which is equal to 15 - [4 + 1 + 0 + 0] - 1 = 9 . Here you calculate the number of sections 7 with the largest part less than 3 plus the number of sections 4 with the largest part less than 2 plus ... The same logic can override this. In the C function (untested!):

 int rank(int part[], int size, int length) { int r = 0; int n = size; int k; for (int i=0; i<length; ++i) { k = part[i]; r += numPar(n,k-1); n -= k; } return numPar(size)-r; } int unrank (int n, int size, int part[]) { int N = size; n = numPar(N)-n-1; int length = 0; int k,p; while (N>0) { for (k=0; k<N; ++k) { p = numPar(N,k); if (p>n) break; } parts[length++] = k; N -= k; n -= numPar(N,k-1); } return length; } 

Here numPar(int n) should return the number of partitions n , and numPar(int n, int k) should return the number of partitions n with the largest part no more than k . You can write them yourself using recursive relationships.

Answer 2

 #include <stdio.h> // number of combinations to divide by the number of k below n int partition(int n, int k){ int p,i; if(n<0) return 0; if(n<2 || k==1) return 1; for(p=0,i=1;i<=k;i++){ p+=partition(ni,i); } return p; } void part_nth_a(int n, int k, int nth){ if(n==0)return; if(n== 1 || n==k && nth == 0){ printf("%d ", n); return ; } int i, diff; for(i=0;i<k;++i){ diff = partition(n, ki) - partition(n, ki-1); if(nth < diff){ printf("%d ", ki); n -= (ki); if(diff == 1) part_nth_a(n, ki, 0); else part_nth_a(n, ki, nth); return; } nth -= diff; } } void part_nth(int n, int nth){ if(nth == 0){ printf("%d ", n); return ; } int i, j, numOfPart; for(i=1;i<n;++i){ numOfPart = ni < i ? partition(i, ni) : partition(i, i); if(nth <= numOfPart) break; nth -= numOfPart; } printf("%d ", ni); if(ni < i) part_nth_a(i, ni, nth-1); else part_nth_a(i, i, nth-1); } int main(){ int n = 7; int i, numOfPart = partition(n, n); for(i=0;i<numOfPart;++i){ printf("%2d ( ", i); part_nth(n, i); printf(")\n"); } return 0; }