如何（便宜）计算N个可能的元素的所有可能的长度-R组合 [英] How to (cheaply) calculate all possible length-r combinations of n possible elements

问题描述

什么是计算N个可能的元素的所有可能的长度-R组合，而无需诉诸蛮力技术或任何以最快的方式，要求STL？

在上Apriori算法在为我最后的项目在我的数据结构类，我开发了一个使用位移和递归，我将在下面的人谁是有兴趣的答案共用一个有趣的解决方案。然而，这是实现这一目标（不使用任何公共库）的最快的方法？

我提出更多好奇的比什么都重要，因为算法我现在有工作就好了，我的目的。

解决方案

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

 无效r_nCr（const的无符号整型和放大器; startNum，const的无符号整型和放大器; bitVal，const的无符号整型和放大器; testNum）//应该与参数（2 ^ R）被称为-1 ，2 ^（R-1），2 ^（N-1）
{
    无符号整数N =（startNum  -  bitVal）LT;＆LT; 1;
    N + = bitVal？ 1：0;    为（unsigned int类型I = LOG2（testNum）+ 1; I＆GT; 0;我 - ）//输出组合成一系列的1和0的
        COUT＆LT;＆LT; （正＆GT;＆GT（I  -  1）及1）;
    COUT＆LT;＆LT; ENDL;    如果（（N放大器;！testNum）及＆放大器;！N = startNum）
        r_nCr（N，bitVal，testNum）;    如果（bitVal＆安培;＆安培; bitVal＆LT; testNum）
        r_nCr（startNum，bitVal＆GT;大于1，testNum）;
}
 

如何工作的：

此函数将元件的各组合作为一和零的序列，然后可以相对于pssed到一组可能的元素的前$ P $（但并不在此特定示例）。

例如，3C2的结果（长-2从一组3种可能的所有元素组合）可以作为pssed 011，110 EX $ P $和101。如果所有可能的元素是{A ，B，C}，则结果可能是对于pssed这一套作为前$ p $ {B，C}，{A，B}和{A，C}

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

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

• 第一个参数是最小的整数，其二进制重新presentation有个1等于我们所创造的组合的长度。这是出生成组合起始值。为5C3，这将是00111b，或十进制7




• 第二个参数是它被设置为1在起始号码的最高位的值。这是创建组合时，这将被减去的第一位。对于5C3，这是正确的，它有4个值第三位。




• 第三个参数是从右侧，其中n是我们结合可能的元素数的第n个位的值。这个数字将被按位与运算，我们创建查询的组合的最左边的位是1还是0。对于5C3，我们将使用第5比特从右边，这是10000B，或16的组合（十进制）。

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

1. 计算startNum - bitVal，位移一格到左边，并添加1，如果bitVal不为0

有关的第一次迭代，结果应该是相同的startNum。这使我们可以在函数内打印出第一组合（这等于startNum），所以我们不必做手工的时间提前。发生此操作的数学如下：

  00111  -  00100 = 00011
00011＆LT;＆LT; 1 = 00110
00110 + 1 = 00111
 

<醇开始=2>

的previous计算的结果是一个新的组合。做一些与此数据。

我们将要打印结果到控制台。这是利用一对环路的可变开出等于我们正在使用的比特数进行（通过取testNum的LOG2并加入1计算; LOG2（16）+ 1 = 4 + 1 = 5），并在结束0每次迭代，我们位右移I-1和打印由最右边的位和ING与1.在这里，结果是数学：

  I = 5：
00111＆GT;＆GT; 4 = 00000
00000安培; 00001 = 0我= 4：
00111＆GT;＆GT; 3 = 00000
00000安培; 00001 = 0我= 3：
00111＆GT;＆GT; 2 = 00001
00001＆安培; 00001 = 1我= 2：
00111＆GT;＆GT; 1 = 00011
00011＆安培; 00001 = 1I = 1：
00111＆GT;＆GT; 0 = 00111
00111＆安培; 00001 = 1输出：00111
 

<醇开始=3>

如果N（步骤1中的计算结果）的最左边的位是0，n是不等于startNum，我们递归具有n作为新的startNum

显然，这将在第一次循环被跳过，因为我们已经表明，n等于startNum。这将成为重要的后续迭代中，我们将在后面看到。

<醇开始=4>

如果bitVal比testNum大于0，小于，用递归当前迭代的原始startNum作为第一个参数。第二个参数是bitVal右移1（同样的事情由2整除）。

我们现在与新bitVal设定为下一个位为当前bitVal右边的值递归。这下一个位是什么将在下次迭代中减去

继续递归，直到bitVal变为等于零。

由于bitVal是正确的第二递归调用位移由一个，我们最终将达到一个点时bitVal等于0。该算法扩展为一棵树，并且当bitVal等于零和最左边的位是1，我们回到我们目前的位置上升一层。最终，这瀑布的所有回来的路上了根。

在这个例子中，树具有3子树和6叶节点。现在我将逐步通过第一子树，它由1根结点和3叶节点。

我们将开始在第一迭代的最后一行，这是

 如果（bitVal）
        r_nCr（startNum，bitVal＆GT;大于1，testNum）;
 

因此​​，我们现在进入与第二迭代startNum = 00111（7），bitVal = 00010（2），和testNum = 10000（16）（这个编号不会改变）。

第二次迭代

第1步：

  N = 00111  -  00010 = 00101 //减去bitVal
N = 00101＆LT;＆LT; 1 = 01010 //左移
N = 01010 + 1 = 01011 // bitVal不为0，所以加1
 

第二步：打印结果

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

第三次迭代

第1步：

  N = 01011  -  00010 = 01001 //减去bitVal
N = 01001＆LT;＆LT; 1 = 10010 //左移
N = 10010 + 1 = 10011 // bitVal不为0，所以加1
 

第二步：打印结果

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

步骤4：bitVal不为0，所以用bitVal递归右移1。现在，我们进入与startNum = 01011（11），bitVal = 00001（1），和testNum = 10000（16）<第四迭代。 / p>

第四次迭代

第1步：

  N = 01011  -  00001 = 01010 //减去bitVal
N = 01010＆LT;＆LT; 1 = 10100 //左移
N = 10100 + 1 = 10101 // bitVal不为0，所以加1
 

第二步：打印结果

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

步骤4：bitVal不为0，所以用bitVal递归右移1。现在，我们进入与startNum = 01011（11），bitVal = 00000（0），和testNum = 10000（16）<第五迭代。 / p>

第五迭代

第1步：

  N = 01011  -  00000 = 01011 //减去bitVal
N = 01011＆LT;＆LT; 1 = 10110 //左移
N = 10110 + 0 = 10110 // bitVal为0，所以加0
//因为bitVal = 0，没有什么是减去或加上;这一步只是变成一条直线位移位1离开。
 

第二步：打印结果

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

第4步：bitVal是0，所以不递归

。

返回第二次迭代

步骤4：bitVal不为0，所以用bitVal递归由1右移

。

这将继续，直到bitVal = 0树的第一层，我们回到第一次迭代，在这一点上，我们将完全从函数返回。

下面是显示功能的树状扩展一个简单的图表：

这是显示执行的功能的线程更复杂的图：

下面是使用替代版本按位或到位加法和按位异或代替减法的：

 无效r_nCr（const的无符号整型和放大器; startNum，const的无符号整型和放大器; bitVal，const的无符号整型和放大器; testNum）//应该与参数（2 ^ R）被称为-1 ，2 ^（R-1），2 ^（N-1）
{
    无符号整数N =（startNum ^ bitVal）LT;＆LT; 1;
    N | =（bitVal！= 0）;    为（unsigned int类型I = LOG2（testNum）+ 1; I＆GT; 0;我 - ）//输出组合成一系列的1和0的
        COUT＆LT;＆LT; （正＆GT;＆GT（I  -  1）及1）;
    COUT＆LT;＆LT; ENDL;    如果（（N放大器;！testNum）及＆放大器;！N = startNum）
        r_nCr（N，bitVal，testNum）;    如果（bitVal＆安培;＆安培; bitVal＆LT; testNum）
        r_nCr（startNum，bitVal＆GT;大于1，testNum）;
}
 

What is the fastest way to calculate all possible length-r combinations of n possible elements without resorting to brute force techniques or anything that requires STL?

While working on an Apriori algorithm for my final project in my data structures class, I developed an interesting solution that uses bit-shifting and recursion, which i will share in an answer below for anyone who is interested. However, is this the fastest way of achieving this (without using any common libraries)?

I ask more out of curiosity than anything else, as the algorithm i currently have works just fine for my purposes.

解决方案

Here is the algorithm that i developed to solve this problem. It currently just outputs each combination as a series of ones and zeros, but can be easily adapted to create data sets based on an array of possible elements.

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

How it works:

This function treats each combination of elements as a sequence of ones and zeros, which can then be expressed with respect to a set of possible elements (but is not in this particular example).

For example, the results of 3C2 (all combinations of length-2 from a set of 3 possible elements) can be expressed as 011, 110, and 101. If the set of all possible elements is {A, B, C}, then the results can be expressed with respect to this set as {B, C}, {A, B}, and {A, C}.

For this explanation, i will be calculating 5C3 (all length-3 combinations composed of 5 possible elements).

This function accepts 3 arguments, all of which are unsigned integers:

• The first parameter is the smallest possible integer whose binary representation has a number of 1s equal to the length of the combinations we're creating. This is out starting value for generating combinations. For 5C3, this would be 00111b, or 7 in decimal.

• The second parameter is the value of highest bit that is set to 1 in the starting number. This is the first bit that will be subtracted when creating the combinations. For 5C3, this is the third bit from the right, which has a value of 4.

• The third parameter is the value of the nth bit from the right, where n is the number of possible elements that we are combining. This number will be bitwise-anded with the combinations we create to check whether the left-most bit of the combination is a 1 or a 0. For 5C3, we will use the 5th bit from the right, which is 10000b, or 16 in decimal.

Here are the actual steps that the function performs:

1. Calculate startNum - bitVal, bit-shift one space to the left, and add 1 if bitVal is not 0.

For the first iteration, the result should be the same as startNum. This is so that we can print out the first combination (which is equal to startNum) within the function so we don't have to do it manually ahead of time. The math for this operation occurs as follows:

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

2. The result of the previous calculation is a new combination. Do something with this data.

We are going to be printing the result to the console. This is done using a for-loop whose variable starts out equal to the number of bits we are working with (calculated by taking log2 of the testNum and adding 1; log2(16) + 1 = 4 + 1 = 5) and ends at 0. Each iteration, we bit-shift right by i-1 and print the right-most bit by and-ing the result with 1. Here is the math:

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. If the left-most bit of n (the result of the calculation in step 1) is 0 and n is not equal to startNum, we recurse with n as the new startNum.

Obviously this will be skipped on the first iteration, as we have already shown that n is equal to startNum. This becomes important in subsequent iterations, which we will see later.

4. If bitVal is greater than 0 and less than testNum, recurse with the current iteration's original startNum as the first argument. Second argument is bitVal shifted right by 1 (same thing as integer division by 2).

We now recurse with the new bitVal set to the value of the next bit to the right of the current bitVal. This next bit is what will be subtracted in the next iteration.

5. Continue to recurse until bitVal becomes equal to zero.

Because bitVal is bit-shifted right by one in the second recursive call, we will eventually reach a point when bitVal equals 0. This algorithm expands as a tree, and when bitVal equals zero and the left-most bit is 1, we return to one layer up from our current position. Eventually, this cascades all the way back the the root.

In this example, the tree has 3 subtrees and 6 leaf nodes. I will now step through the first subtree, which consists of 1 root node and 3 leaf nodes.

We will start at the last line of the first iteration, which is

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

So we now enter the second iteration with startNum=00111(7), bitVal = 00010(2), and testNum = 10000(16) (this number never changes).

Second Iteration

Step 1:

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

Step 2: Print result.

Step 3: The left-most bit is 0 and n is not equal to startNum, so we recurse with n as the new startNum. We now enter the third iteration with startNum=01011(11), bitVal = 00010(2), and testNum = 10000(16).

Third Iteration

Step 1:

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

Step 2: Print result.

Step 3: The left-most bit is 1, so do not recurse.

Step 4: bitVal is not 0, so recurse with bitVal shifted right by 1. We now enter the fourth iteration with startNum=01011(11), bitVal = 00001(1), and testNum = 10000(16).

Fourth Iteration

Step 1:

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

Step 2: Print result.

Step 3: The left-most bit is 1, so do not recurse.

Step 4: bitVal is not 0, so recurse with bitVal shifted right by 1. We now enter the fifth iteration with startNum=01011(11), bitVal = 00000(0), and testNum = 10000(16).

Fifth Iteration

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

Step 2: Print result.

Step 3: The left-most bit is 1, so do not recurse.

Step 4: bitVal is 0, so do not recurse.

Return to Second Iteration

Step 4: bitVal is not 0, so recurse with bitVal shifted right by 1.

This will continue on until bitVal = 0 for the first level of the tree and we return to the first iteration, at which point we will return from the function entirely.

Here is a simple diagram showing the function's tree-like expansion:

And here is a more complicated diagram showing the function's thread of execution:

Here is an alternate version using bitwise-or in place of addition and bitwise-xor in place of subtraction:

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

这篇关于如何（便宜）计算N个可能的元素的所有可能的长度-R组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！