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).

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.