Find the lexicographic order of an integer partition

Question

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

Now I want to do the same thing for integer partitions of N. For example, for N=7, I want to be able to back and forth between the index (left) and the partition (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've tried a few 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 seems to be on the right track. I came up with this because it sort of counts how many times I have to move a number down (like 6,3,2 goes to 6,3,1,1). I can't see how to fix it, though, because I don't know how to account for when things have to get recombined (like 6,3,1,1 goes to 6,2,2).

• ryyker: Can you show the code that calls the segment shown?
• Daniel: @ryyker which part? i just used printf to print the bad index, good index and partition, but i can include that if it help.
• kuroi neko: If I understand correctly, this boils down to generating a lexicographically sorted list of the integer partitions, right?
• Daniel: @kuroineko No. I want to be able to get the nth partition without computing the ones before it.
• kuroi neko: Okay, so you want a function to compute the Nth partition on the fly, with minimal time and/or memory consumption, and another that can give you the sorted index of a given partition, right?

Answer 1

Think about why the "factorial decomposition" works for permutations, and the same logic works here. However, instead of using k! for the number of permutations of k objects, you must use the partition function p(n,k) for the number of partitions of n with largest part at most 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 of (3,2,1,1), for example, you compute

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 15 - [4 + 1 + 0 + 0] - 1 = 9. Here you're computing the number of partitions of 7 with largest part less than 3 plus the number of partitions of 4 with largest part less than 2 plus ... The same logic can reverse this. In C, the (untested!) functions are:

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 of n, and numPar(int n, int k) should return the number of partitions of n with largest part at most k. You can write these yourself using recurrence relations.

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(n-i,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, k-i) - partition(n, k-i-1);
 if(nth < diff){
 printf("%d ", k-i);
 n -= (k-i);
 if(diff == 1)
 part_nth_a(n, k-i, 0);
 else
 part_nth_a(n, k-i, 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 = n-i < i ? partition(i, n-i) : partition(i, i);
 if(nth <= numOfPart)
 break;
 nth -= numOfPart;
 }
 printf("%d ", n-i);
 if(n-i < i)
 part_nth_a(i, n-i, 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;
}