combinatorics - 将一个整数的所有组合生成 k 个部分

Question

我无法弄清楚如何将整数 N 的所有组合（http://en.wikipedia.org/wiki/Composition_%28number_theory%29）生成为 K 部分，但一次只做一个。也就是说，我需要一个函数，给定生成的前一个组合，返回序列中的下一个组合。原因是我的应用程序的内存有限。如果我可以使用 Python 及其生成器功能，这会容易得多，但我坚持使用 C++。

这类似于n 到 k 部分的 Next Composition - 有人有有效的算法吗？

任何帮助将不胜感激。

Answer 1

你可以尝试这样的事情：

从 (K-1) 个数组 [1,1,...,1,N-k+1] 和余数的 1 个条目开始。可以通过增加第 (K-1) 个元素并减少最后一个元素来创建下一个组合。只要最后一个元素大于倒数第二个元素，就执行此技巧。

当最后一个元素变小时，增加第（K-2）个元素，将第（K-1）个元素设置为相同的值，然后再次将最后一个元素设置为余数。重复该过程并在必要时对其他元素应用相同的原则。

您最终会得到一个不断排序的数组，以避免重复的组合

Answer 2

初步意见

首先从观察开始，即 [1,1,...,1,n-k+1] 是 n 超过 k 个部分的第一个组合（按字典顺序），并且 [n-k+1,1,1, ...,1] 是最后一个。

现在考虑一个例子：合成[2,4,3,1,1]，这里n = 11，k = 5。按字典顺序排列的下一个是哪个？显然最右边要增加的部分是 4，因为 [3,1,1] 是 5 超过 3 部分的最后一个组合。

4在3的左边，最右边的部分与1不同。

所以把 4 变成 5，把 [3,1,1] 替换为 [1,1,2]，余数 (3+1+1)-1 的第一个组成，得到 [2,5,1,1, 2]

生成程序（C 语言）

以下 C 程序显示如何按字典顺序按需计算此类组合

#include <stdio.h>
#include <stdbool.h>

bool get_first_composition(int n, int k, int composition[k])
{
    if (n < k) {
        return false;
    }
    for (int i = 0; i < k - 1; i++) {
        composition[i] = 1;
    }
    composition[k - 1] = n - k + 1;
    return true;
}

bool get_next_composition(int n, int k, int composition[k])
{
    if (composition[0] == n - k + 1)    {
        return false;
    }
    // there'a an i with composition[i] > 1, and it is not 0.
    // find the last one
    int last = k - 1;
    while (composition[last] == 1) {
        last--;
    }
    // turn    a b ...   y   z 1 1 ...   1
    //                       ^ last
    // into    a b ... (y+1) 1 1 1 ... (z-1)

    // be careful, there may be no 1's at the end

    int z = composition[last];
    composition[last - 1] += 1;
    composition[last] = 1;
    composition[k - 1] = z - 1;
    return true;
}

void display_composition(int k, int composition[k])
{
    char *separator = "[";
    for (int i = 0; i < k; i++) {
        printf("%s%d", separator, composition[i]);
        separator = ",";
    }
    printf("]\n");
}


void display_all_compositions(int n, int k)
{
    int composition[k];  // VLA. Please don't use silly values for k
    for (bool exists = get_first_composition(n, k, composition);
            exists;
            exists = get_next_composition(n, k, composition)) {
        display_composition(k, composition);
    }
}

int main()
{
    display_all_compositions(5, 3);
}

结果

[1,1,3]
[1,2,2]
[1,3,1]
[2,1,2]
[2,2,1]
[3,1,1]

弱成分

类似的算法适用于弱组合（允许为 0）。

bool get_first_weak_composition(int n, int k, int composition[k])
{
    if (n < k) {
        return false;
    }
    for (int i = 0; i < k - 1; i++) {
        composition[i] = 0;
    }
    composition[k - 1] = n;
    return true;
}

bool get_next_weak_composition(int n, int k, int composition[k])
{
    if (composition[0] == n)    {
        return false;
    }
    // there'a an i with composition[i] > 0, and it is not 0.
    // find the last one
    int last = k - 1;
    while (composition[last] == 0) {
        last--;
    }
    // turn    a b ...   y   z 0 0 ...   0
    //                       ^ last
    // into    a b ... (y+1) 0 0 0 ... (z-1)

    // be careful, there may be no 0's at the end

    int z = composition[last];
    composition[last - 1] += 1;
    composition[last] = 0;
    composition[k - 1] = z - 1;
    return true;
}

n=5 k=3 的结果

[0,0,5]
[0,1,4]
[0,2,3]
[0,3,2]
[0,4,1]
[0,5,0]
[1,0,4]
[1,1,3]
[1,2,2]
[1,3,1]
[1,4,0]
[2,0,3]
[2,1,2]
[2,2,1]
[2,3,0]
[3,0,2]
[3,1,1]
[3,2,0]
[4,0,1]
[4,1,0]
[5,0,0]

可以将类似的算法编写为将 n 组合成大于某个固定值的 k 部分。