c++ - the different combinations of a vector's values

Question

Suppose I have a vector of n values, I want to get the different combinations of its values, for example: if I have vect = [a, b, c] the different combinations that I want are: [a, b, c], [a,b], [a,c], [b,c], [a], [b], [c]

Note that for example [a,b] is the same as [b,a] so I don't need to keep both of them.

Answer 1

Count from 0 to 2^vector.size() - 1. If bit i of your loop variable is 1, include vector[i] in your combination.

vector<char> v;
v.push_back('a');
v.push_back('b');
v.push_back('c');
for (int counter = 0; counter < (1 << v.size()); ++counter)
{
    vector<char> combination;
    for (int i = 0; i < v.size(); ++i)
    {
        if (counter & (1 << i))
            combination.push_back(v[i]);
    }

    // do something with combination
}

Edit: if you want to exclude the empty set, start counting at 1.

Answer 2

Give you a pseudo code, please convert it to real code.

vector resultVec;
while (!inputVec.empty)
{
    char c = inputVec.pop_back();

    foreach(one in resultVec)
    {
         combined = combine c and one;
         resultVec.push_back(combined);
    }

    resultVec.push_back(c);
}

Answer 3

Imagine you have a function which can already do this for you. Let's call it combinations.

If you were going to implement your own version of this, my_combinations, you could do it by looking at the first element in your vector, calling combinations on the rest of the vector, and then combining your element with each of the combinations.

Once you'd implemented this, you could delegate to your own version of combinations instead of using the pre-existing one.