algorithm - 给定索引号，是否有生成特定 n Multichoose r 组合的函数？

Question

例如3 multichoose 2有以下组合:

i   combo
0 = [0,0]
1 = [0,1]
2 = [0,2]
3 = [1,1]
4 = [1,2]
5 = [2,2]

是否可以编写一个函数，其参数为 n、r、i 并返回有问题的组合，而无需遍历它之前的每个组合？

Answer 1

Could a function be written whose arguments are n,r,i and returns the combination in question, without iterating through every combination before it?

是的。我们必须做一些计算才能找到这个问题的核心。为了更好地说明如何将其分解为非常简单的小问题，我们将看一个更大的例子。一次考虑 5 选 3 的所有组合，不重复(我们将从这里开始说 5 选 3)。

      [,1] [,2] [,3]
 [1,]    1    2    3
 [2,]    1    2    4
 [3,]    1    2    5
 [4,]    1    3    4
 [5,]    1    3    5
 [6,]    1    4    5
 [7,]    2    3    4
 [8,]    2    3    5
 [9,]    2    4    5
[10,]    3    4    5

注意前 6 行。如果我们移除这 6 行的第一列并从每个元素中减去 1，我们得到:

      [,1] [,2]                   [,1] [,2]
[1,]    2    3              [1,]    1    2
[2,]    2    4  subtract 1  [2,]    1    3
[3,]    2    5    --->>>>   [3,]    1    4
[4,]    3    4              [4,]    2    3
[5,]    3    5              [5,]    2    4
[6,]    4    5              [6,]    3    4

右边的矩阵恰好是 4 选 2 的所有组合。继续，我们看到“第二”组(即原始矩阵的第 7 行到第 9 行)看起来也有顺序:

     [,1] [,2]                    [,1] [,2]
[1,]    3    4              [1,]    1    2
[2,]    3    5  subtract 2  [2,]    1    3
[3,]    4    5    --->>>>   [3,]    2    3

这只是 3 选 2。我们开始看到一种模式展开。也就是说，所有较小的 n 和 r 的组合都包含在我们的父组合中。当我们向右移动时，这种模式会继续。剩下的就是跟上我们所追求的组合。

以下是用 C++ 编写的上述算法(注意，没有任何数据验证):

template <typename T>
double nChooseK(T n, T k) {
    // Returns number of k-combinations from n elements.
    // Mathematically speaking, we have: n!/(k!*(n-k)!)
    if (k == n || k == 0)
        return 1;
    else if (k > n || n < 0)
        return 0;

    double nCk;
    double temp = 1;
    for (int i = 1; i <= k; i++)
        temp *= (double) (n - k + i) / i;

    nCk = std::round(temp);
    return nCk;
}

std::vector<int> nthCombination(int n, int r, double i) {

    int j = 0, n1 = n - 1, r1 = r - 1;
    double temp, index1 = i, index2 = i;
    std::vector<int> res(r);

    for (int k = 0; k < r; k++) {
        temp = nChooseK(n1, r1);
        while (temp <= index1) {
            index2 -= nChooseK(n1, r1);
            n1--;
            j++;
            temp += nChooseK(n1, r1);
        }
        res[k] = j;
        n1--;
        r1--;
        j++;
        index1 = index2;
    }

    return res;
}

在我们上面的例子中用 5 选 3 调用它，我们得到:

nthCombination(5, 3, 0) -->> 0 1 2
nthCombination(5, 3, 1) -->> 0 1 3
nthCombination(5, 3, 2) -->> 0 1 4
nthCombination(5, 3, 3) -->> 0 2 3
nthCombination(5, 3, 4) -->> 0 2 4
nthCombination(5, 3, 5) -->> 0 3 4
nthCombination(5, 3, 6) -->> 1 2 3
nthCombination(5, 3, 7) -->> 1 2 4
nthCombination(5, 3, 8) -->> 1 3 4
nthCombination(5, 3, 9) -->> 2 3 4

这种方法也非常有效。下面，我们立即得到第 10 亿个组合 40 选 20(这产生了超过 1000 亿个组合):

      // N.B. base zero so we need to subtract 1
nthCombination(40, 20, 1000000000 - 1)  -->>
   0  1  2  3  4  5  8  9 14 16 18 20 22 23 31 33 34 35 38 39

编辑

正如 OP 在评论中指出的那样，他们给出了一个重复的例子。解决方案非常相似，分解为计数。我们首先需要一个类似于 nChooseK 但考虑重复的计数函数。下面的函数就是这样做的:

double combsWithReps(int n, int r) {
    // For combinations where repetition is allowed, this
    // function returns the number of combinations for
    // a given n and r. The resulting vector, "triangleVec"
    // resembles triangle numbers. In fact, this vector
    // is obtained in a very similar method as generating
    // triangle numbers, albeit in a repeating fashion.

    if (r == 0)
        return 1;

    int i, k;
    std::vector<double> triangleVec(n);
    std::vector<double> temp(n);

    for (i = 0; i < n; i++)
        triangleVec[i] = i+1;

    for (i = 1; i < r; i++) {
        for (k = 1; k <= n; k++)
            temp[k-1] = std::accumulate(triangleVec.begin(), triangleVec.begin() + k, 0.0);

        triangleVec = temp;
    }

    return triangleVec[n-1];
}

下面是生成第 ith<​​ 次组合的函数。

std::vector<int> nthCombWithRep(int n, int r, double i) {

    int j = 0, n1 = n, r1 = r - 1;
    double temp, index1 = i, index2 = i;
    std::vector<int> res(r);

    for (int k = 0; k < r; k++) {
        temp = combsWithReps(n1, r1);
        while (temp <= index1) {
            index2 -= combsWithReps(n1, r1);
            n1--;
            j++;
            temp += combsWithReps(n1, r1);
        }
        res[k] = j;
        r1--;
        index1 = index2;
    }

    return res;
}

它与上面的第一个功能非常相似。您会注意到 n1-- 和 j++ 从函数的末尾删除，并且 n1 被初始化为 n 而不是 n - 1。

这是上面的例子:

nthCombWithRep(40, 20, 1000000000 - 1)  -->>
    0  0  0  0  0  0  0  0  0  0  0  4  5  6  8  9 12 18 18 31