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.

现在我想要做同样的事情为 N 整数分区。例如， N = 7 ，我希望能够索引（左）和分区之间来回（右）：

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 )

这完全不是那么回事，但似乎是在正确的轨道。我想出了这样的，因为它计算多少次，我要搬到一个数字向下（如 6,3,2 进入 6， 3,1,1 ）。我看不出如何解决它，但是，因为我不知道该如何解释，当事情已经得到重组（如 6,3,1,1 进入 6,2,2 ）。

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

推荐答案

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

要获得的字典指数（3,2,1,1），比如你计算

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

这是 15 - [4 + 1 + 0 + 0] - 1 = 9 。在这里，我们计算的7大一部分分区小于3的数量加4个分区具有最大的部分不到2加......同样的逻辑可以扭转这个数。在C中，（！未经测试）功能是：

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.