如何（便宜地）计算n个可能元素的所有可能的长度-r组合

什么是计算n个可能元素的所有可能长度-r组合的最快方法，而不采用powershell技术或任何需要STL的东西？

在我的数据结构类中为我的最终项目开发Apriori算法时，我开发了一个使用位移和递归的有趣解决方案，我将在下面的答案中分享对任何感兴趣的人。 但是，这是实现这一目标的最快方法（不使用任何通用库）吗？

我出于好奇而不是其他任何问题，因为我目前的算法对我的目的来说效果很好。

Answer 1

这是我为解决这个问题而开发的算法。 它目前只是将每个组合输出为一系列1和0，但可以很容易地根据可能元素的数组来创建数据集。

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1) { unsigned int n = (startNum - bitVal) << 1; n += bitVal ? 1 : 0; for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s cout << (n >> (i - 1) & 1); cout << endl; if (!(n & testNum) && n != startNum) r_nCr(n, bitVal, testNum); if (bitVal && bitVal < testNum) r_nCr(startNum, bitVal >> 1, testNum); } 

怎么运行的：

该函数将每个元素组合视为1和0的序列，然后可以相对于一组可能的元素表达（但不在此特定示例中）。

例如，3C2的结果（来自一组3个可能元素的长度为2的所有组合）可以表示为011,110和101.如果所有可能元素的集合是{A，B，C}，那么结果可以表示为{B，C}，{A，B}和{A，C}。

对于这个解释，我将计算5C3（由5个可能元素组成的所有长度-3组合）。

此函数接受3个参数，所有参数都是无符号整数：

• 第一个参数是可能的最小整数，其二进制表示的数量等于我们正在创建的组合的长度。 这是生成组合的起始值。 对于5C3，这将是00111b，或十进制7。

• 第二个参数是在起始编号中设置为1的最高位的值。 这是创建组合时将减去的第一个位。 对于5C3，这是右边的第三个位，其值为4。

• 第三个参数是右起第n位的值，其中n是我们组合的可能元素的数量。 这个数字将与我们创建的组合按位，以检查组合的最左位是1还是0.对于5C3，我们将使用右边的第5位，即10000b或16 in小数。

以下是该函数执行的实际步骤：

1. 计算startNum – bitVal，向左移位一个空格，如果bitVal不为0，则加1。

对于第一次迭代，结果应与startNum相同。 这样我们就可以在函数中打印出第一个组合（等于startNum），这样我们就不必提前手动完成。 此操作的数学运算如下：

 00111 - 00100 = 00011 00011 << 1 = 00110 00110 + 1 = 00111 

2. 先前计算的结果是新组合。 用这些数据做点什么。

我们将把结果打印到控制台。 这是使用for循环完成的，它的变量开始等于我们正在使用的位数（通过获取testNum的log2并加1; log2（16）+ 1 = 4 + 1 = 5计算）并结束于0.每次迭代，我们按i-1进行位移，并通过结果和1打印最右边的位。这是数学：

 i=5: 00111 >> 4 = 00000 00000 & 00001 = 0 i=4: 00111 >> 3 = 00000 00000 & 00001 = 0 i=3: 00111 >> 2 = 00001 00001 & 00001 = 1 i=2: 00111 >> 1 = 00011 00011 & 00001 = 1 i=1: 00111 >> 0 = 00111 00111 & 00001 = 1 output: 00111 

3. 如果n的最左位（步骤1中的计算结果）为0且n不等于startNum，我们将n作为新的startNum递归。

显然，这将在第一次迭代时跳过，因为我们已经certificaten等于startNum。 这在随后的迭代中变得很重要，我们将在后面看到。

4. 如果bitVal大于0且小于testNum，则使用当前迭代的原始startNum作为第一个参数进行递归。 第二个参数是bitVal向右移动1（与整数除以2相同）。

我们现在递归，将新的bitVal设置为当前bitVal右边的下一位的值。 下一位将在下一次迭代中减去。

5. 继续递归直到bitVal等于零。

因为bitVal在第二次递归调用中被右移一位，所以当bitVal等于0时，我们最终会达到一个点。此算法扩展为树，当bitVal等于零且最左边的位为1时，我们返回到从我们目前的位置上升一层。 最终，这种状态一直回到根部。

在此示例中，树具有3个子树和6个叶节点。 我现在将逐步介绍第一个子树，它由1个根节点和3个叶子节点组成。

我们将从第一次迭代的最后一行开始，即

 if (bitVal) r_nCr(startNum, bitVal >> 1, testNum); 

所以我们现在用startNum = 00111（7），bitVal = 00010（2）和testNum = 10000（16）进入第二次迭代（这个数字永远不会改变）。

第二次迭代

步骤1：

 n = 00111 - 00010 = 00101 // Subtract bitVal n = 00101 << 1 = 01010 // Shift left n = 01010 + 1 = 01011 // bitVal is not 0, so add 1 

第2步：打印结果。

第3步：最左边的位是0，n不等于startNum，所以我们用n作为新的startNum递归。 我们现在进入第三次迭代，其中startNum = 01011（11），bitVal = 00010（2），testNum = 10000（16）。

第三次迭代

步骤1：

 n = 01011 - 00010 = 01001 // Subtract bitVal n = 01001 << 1 = 10010 // Shift left n = 10010 + 1 = 10011 // bitVal is not 0, so add 1 

第2步：打印结果。

第3步：最左边的位是1，所以不要递归。

步骤4：bitVal不为0，因此将bitVal向右移动1递归。我们现在进入第四次迭代，其中startNum = 01011（11），bitVal = 00001（1），testNum = 10000（16）。

第四次迭代

步骤1：

 n = 01011 - 00001 = 01010 // Subtract bitVal n = 01010 << 1 = 10100 // Shift left n = 10100 + 1 = 10101 // bitVal is not 0, so add 1 

第2步：打印结果。

第3步：最左边的位是1，所以不要递归。

步骤4：bitVal不为0，因此将bitVal向右移动1递归。我们现在进入第五次迭代，其中startNum = 01011（11），bitVal = 00000（0），testNum = 10000（16）。

第五次迭代

步骤1：

 n = 01011 - 00000 = 01011 // Subtract bitVal n = 01011 << 1 = 10110 // Shift left n = 10110 + 0 = 10110 // bitVal is 0, so add 0 // Because bitVal = 0, nothing is subtracted or added; this step becomes just a straight bit-shift left by 1. 

第2步：打印结果。

第3步：最左边的位是1，所以不要递归。

第4步：bitVal为0，所以不要递归。

返回第二次迭代

第4步：bitVal不为0，因此将bitVal向右移动1递归。

对于树的第一级，这将持续到bitVal = 0，并且我们将返回到第一次迭代，此时我们将完全从函数返回。

这是一个简单的图表，显示了函数的树状扩展：

这是一个更复杂的图表，显示了函数的执行线程：

这是一个替代版本，使用按位或代替加法和bitwise-xor代替减法：

 void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1) { unsigned int n = (startNum ^ bitVal) << 1; n |= (bitVal != 0); for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s cout << (n >> (i - 1) & 1); cout << endl; if (!(n & testNum) && n != startNum) r_nCr(n, bitVal, testNum); if (bitVal && bitVal < testNum) r_nCr(startNum, bitVal >> 1, testNum); } 

Answer 2

那这个呢？

 #include  #define SETSIZE 3 #define NELEMS 7 #define BYTETOBINARYPATTERN "%d%d%d%d%d%d%d%d" #define BYTETOBINARY(byte) \ (byte & 0x80 ? 1 : 0), \ (byte & 0x40 ? 1 : 0), \ (byte & 0x20 ? 1 : 0), \ (byte & 0x10 ? 1 : 0), \ (byte & 0x08 ? 1 : 0), \ (byte & 0x04 ? 1 : 0), \ (byte & 0x02 ? 1 : 0), \ (byte & 0x01 ? 1 : 0) int main() { unsigned long long x = (1 << SETSIZE) -1; unsigned long long N = (1 << NELEMS) -1; while(x < N) { printf ("x: "BYTETOBINARYPATTERN"\n", BYTETOBINARY(x)); unsigned long long a = x & -x; unsigned long long y = x + a; x = ((y & -y) / a >> 1) + y - 1; } }; 

它应该打印7C3。