c - 查找整数分区的字典顺序

Question

对于排列，给定 N 和 k，我有一个函数可以找到 N 的第 k 排列> 按字典顺序。此外，给定一个排列 perm，我有一个函数可以在 N 的所有排列中找到排列的词典索引。为此，我使用了 this answer 中建议的“阶乘分解” .

现在我想对 N 的整数分区做同样的事情。例如，对于 N=7，我希望能够在索引(左)和分区(右)之间来回移动:

 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 )

我已经尝试了一些东西。我想到的最好的是

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

给出以下内容:

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

Answer 1

想想为什么“阶乘分解”适用于排列，同样的逻辑在这里也适用。但是，不是使用 k! 作为 k 对象的排列数，您必须使用分区函数 p(n,k) n 的分区数，最大部分最多 k。对于 n=7，这些数字是:

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。在这里，您要计算最大部分小于 3 的 7 的分区数加上最大部分小于 2 的 4 的分区数加上......相同的逻辑可以颠倒这个。在 C 中，(未经测试!)函数是:

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;
}

这里numPar(int n)应该返回n的分区数，numPar(int n, int k)应该返回n 的分区数，最大部分最多 k。您可以使用递归关系自己编写这些。