给定索引号，是否可以生成特定的n个Multichoose r组合？ [英] Is there a function to generate a specific n Multichoose r combination, given the index number?
问题描述
例如，3个选择2具有以下组合：
For example, 3 multichoose 2 has the following combinations:
i combo
0 = [0,0]
1 = [0,1]
2 = [0,2]
3 = [1,1]
4 = [1,2]
5 = [2,2]
是否可以编写一个参数为n，r，i并返回的函数
Could a function be written whose arguments are n,r,i and returns the combination in question, without iterating through every combination before it?
推荐答案
是否可以编写函数？
Could a function be written whose arguments are n,r,i and returns the combination in question, without iterating through every combination before it?
是的，其参数为n，r，i并返回有问题的组合，而不会迭代之前的每个组合？我们必须做一点点计算才能弄清楚这个问题的核心。为了更好地说明如何将其分解为非常简单的较小问题，我们将看一个较大的示例。考虑一次选择5个3的所有组合，没有重复（我们从这里开始说5个选择3）。
Yes. We have to do a little counting to get at the heart of this problem. To better illustrate how this can be broken down into very simple smaller problems, we will look at a larger example. Consider all combinations of 5 chosen 3 at a time with no repeats (we will say from here on out 5 choose 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，我们将获得：
Notice the first 6 rows. If we remove the first column of these 6 rows and subtract 1 from every element, we obtain:
[,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行）看起来也有顺序：
The matrix on the right is precisely all of the combinations of 4 choose 2. Continuing on, we see that the "second" group (i.e. rows 7 through 9 of the original matrix) also looks to have order:
[,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 的组合都包含在我们的父组合中。随着我们向右移动，此模式继续。剩下的就是跟上我们要遵循的组合。
This is simply 3 choose 2. We are starting to see a pattern unfold. Namely, that all combinations of smaller n and r are contained in our parent combinations. This pattern continues as we move to the right. All that is left is to keep up with which combination we are after.
下面是用 C ++ （注意，没有任何数据验证）：
Below is the above algorithm written out in C++ (N.B. there isn't any data validation):
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进行调用，得到：
Calling it on our example above with 5 choose 3 we obtain:
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
这种方法也非常有效。在下面，我们立即得到40个亿万分之一的组合，选择20（产生超过1000亿个组合）：
This approach is very efficient as well. Below, we get the billionth combination of 40 choose 20 (which generates more than 100 billion combinations) instantly:
// 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 的计数函数，但是要考虑重复。下面的函数就是这样：
Edit
As the OP points out in the comments, they gave an example with repeats. The solution is very similar and it breaks down to counting. We first need a counting function similar to nChooseK but that considers repeats. The function below does just that:
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 。
It is very similar to the first function above. You will notice that n1-- and j++ are removed from the end of the function and also that n1 is initialized to n instead of 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
这篇关于给定索引号，是否可以生成特定的n个Multichoose r组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
