查找字符串矢量的R-组合 [英] Finding r-Combinations of a Vector of Strings

问题描述

我想生成的字符串指定列表中的所有可能的R-组合。例如：

I'm trying to generate all possible r-combination of a given list of strings. For example :

vector<string> original(n);
original[0] = "Brown";
original[1] = "Yellow";
original[2] = "Blue";

在这种情况下，n = 3的（3种颜色），并且例如，如果用户输入R = 2时，程序必须打印

In this case, n = 3 (3 colors), and for example, if the user inputs r = 2, the program must print :

    >Brown, Yellow
    >Brown, Blue
    >Yellow, Blue

每个人我接触过的蓝色表示使用next_permutation路线，但是，让我重复（我找的组合，没有排列.....所以在上面的例子中，一组（黄，蓝）后，（ ，黄）不应该被包括在内）。

Everyone I have talked to says to use the next_permutation route but that gives me repetition (I am looking for combinations, not permutations..... so in the example above, after the set (Yellow, Blue), (Blue, Yellow) should not be included).

推荐答案

请尝试以下步骤：

1）创建一个系列的第3位。

1) Create a series of 3 bits.

2）由于研究 2，初始化两个最右边的位为1。

2) Since r is 2, initialize the two rightmost bits to 1.

3）输出，与那些对位对应，例如，如果 bitarray [0] 1，则输出的向量中的项原创[0] ，如果 bitarray [1] 1，则输出原创[1] 等。

3) Output the items in the vector that correspond with the bits that are on, for example, if bitarray[0] is 1, then output original[0], if bitarray[1] is 1, then output original[1], etc.

4）呼叫 next_permutation（）对位获得下一个位模式。

4) Call next_permutation() on the bits to get the "next" bit pattern.

重复步骤3和4，直到next_permutation（）是假。

Repeat steps 3 and 4 until next_permutation() is false.

因此​​，基本上，你需要的 N 项目位数组，开始了与初始化右侧的研究位1。然后，可以使用 next_permutation 更改位模式。我建议你​​这样做在纸上先，看到所有它是如何工作。

So basically, you need a bit array of n items to start off with and initialize the rightmost r bits to 1. Then you use next_permutation to change the bit pattern. I recommend you do this on paper first, to see how it all works.

下面是一个例子。这是硬codeD的3个项目，所以把它的它的价值。

Below is an example. It is hard-coded for 3 items, so take it for what it's worth.

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

void OutputVector (const std::vector<std::string>& theVect, bool* bArray, int nItems)
{
    for (int i = 0; i < nItems; ++i)
       if (bArray[i] == true)
         std::cout << theVect[i] << " ";
    std::cout << "\n";
}

using namespace std;

int main()
{
    std::vector<std::string> original = { "Brown", "Yellow", "Blue" };
    bool myBits[3] = { false };  // everything is false now
    myBits[1] = myBits[2] = true;  // set rightmost bits to true
    do  // start combination generator
    {
       OutputVector(original, myBits, 3);
    } while (next_permutation(myBits, myBits + 3));  // change the bit pattern
}

以你的例子：

Taking your example:

我们开始与该位模式（称之为位的阵列 bitArray ）： 011

We start out with this bit pattern (call the array of bits bitArray): 011

这意味着我们输出原创[1] 和原[2] ，因为 bitArray [1] 和 bitArray [2] 是真（设置为1）。

This means we output original[1] and original[2] because bitArray[1] and bitArray[2] are "true" (set to 1).

在 next_permutation 上调用这些位，位模式变为这样： 101

When next_permutation is called on these bits, the bit pattern changes to this: 101

我们输出原创[0] 和原[2] ，因为 bitArray [0 ] 和 bitArray [2] 是真实的。

We output original[0] and original[2] because bitArray[0] and bitArray[2] are "true".

next_permutation 被调用时，位排列的变化： 110

next_permutation is called, bit array changes: 110

原创[0] 和原创[1] 输出。

next_permutation 将返回一个错误，如果再次调用，因为没有更多的排列。

next_permutation will return a false if called again, since there are no more permutations.

完成。

这篇关于查找字符串矢量的R-组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！