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.