Finding r-Combinations of a Vector of Strings

Question

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";

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

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

Answer 1

My solution, which is faster than using std::next_permutation:

#include "../combinations/combinations"
#include <iostream>
#include <string>
#include <vector>

int
main()
{
    std::vector<std::string> original(6);
    original[0] = "Brown";
    original[1] = "Yellow";
    original[2] = "Blue";
    original[3] = "Red";
    original[4] = "Green";
    original[5] = "Purple";
    for_each_combination(original.begin(), original.begin()+3, original.end(),
                         [](auto begin, auto end)
                         {
                              std::cout << "{";
                              bool print_comma = false;
                              for (; begin != end; ++begin)
                              {
                                   if (print_comma)
                                       std::cout << ", ";
                                   print_comma = true;
                                   std::cout << *begin;
                              }
                              std::cout << "}\n";
                              return false;
                         });
}

Find for_each_combination here.

Output:

{Brown, Yellow, Blue}
{Brown, Yellow, Red}
{Brown, Yellow, Green}
{Brown, Yellow, Purple}
{Brown, Blue, Red}
{Brown, Blue, Green}
{Brown, Blue, Purple}
{Brown, Red, Green}
{Brown, Red, Purple}
{Brown, Green, Purple}
{Yellow, Blue, Red}
{Yellow, Blue, Green}
{Yellow, Blue, Purple}
{Yellow, Red, Green}
{Yellow, Red, Purple}
{Yellow, Green, Purple}
{Blue, Red, Green}
{Blue, Red, Purple}
{Blue, Green, Purple}
{Red, Green, Purple}

If constrained to C++98, or if you simply prefer named functions, you can do:

#include "../combinations/combinations"
#include <iostream>
#include <string>
#include <vector>

bool
print(std::vector<std::string>::const_iterator begin,
      std::vector<std::string>::const_iterator end)
{
    std::cout << "{";
    bool print_comma = false;
    for (; begin != end; ++begin)
    {
        if (print_comma)
            std::cout << ", ";
        print_comma = true;
        std::cout << *begin;
    }
    std::cout << "}\n";
    return false;
}

int
main()
{
    std::vector<std::string> original(6);
    original[0] = "Brown";
    original[1] = "Yellow";
    original[2] = "Blue";
    original[3] = "Red";
    original[4] = "Green";
    original[5] = "Purple";
    for_each_combination(original.begin(), original.begin()+3, original.end(),
                         print);
}

Source code is open source under the boost software license, but is not part of boost. Feel free to use. The intent is that this source code should be free to use, and free use is encouraged. If your lawyers aren't happy with this license, let me know and I will try to make them happy, gratis.

The same link includes:

template <class BidirIter, class Function>
Function
for_each_permutation(BidirIter first,
                     BidirIter mid,
                     BidirIter last,
                     Function f);

template <class BidirIter, class Function>
Function
for_each_reversible_permutation(BidirIter first,
                                BidirIter mid,
                                BidirIter last,
                                Function f);

template <class BidirIter, class Function>
Function
for_each_circular_permutation(BidirIter first,
                              BidirIter mid,
                              BidirIter last,
                              Function f);

template <class BidirIter, class Function>
Function
for_each_reversible_circular_permutation(BidirIter first,
                                         BidirIter mid,
                                         BidirIter last,
                                         Function f);

template <class BidirIter, class Function>
Function
for_each_combination(BidirIter first,
                     BidirIter mid,
                     BidirIter last,
                     Function f);

And the code is fast.

Answer 2

Try these steps:

1) Create a series of 3 bits.

2) Since r is 2, initialize the two rightmost bits to 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) Call next_permutation() on the bits to get the "next" bit pattern.

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

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.

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:

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

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

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

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

next_permutation is called, bit array changes: 110

original[0] and original[1] are output.

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

Done.

Answer 3

You may use the something like the following:

template <typename T>
void Combination(const std::vector<T>& v, std::size_t count)
{
    assert(count <= v.size());
    std::vector<bool> bitset(v.size() - count, 0);
    bitset.resize(v.size(), 1);

    do {
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                std::cout << v[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (std::next_permutation(bitset.begin(), bitset.end()));
}

Live example