C++ All combinations of a vector

Question

Lets say we have some numbers from 0 to n, we want to scramble those in size s and want to see every possible combination.

So the number of permutations happens to be equal to s! * n!/(s!*(n-s)!).

Example with n = 3 and s = 3:

0 1 2 | 0 1 3 | 0 2 1 | 0 2 3 | 0 3 1 | 0 3 2 | 1 0 2 | 1 0 3 | 1 3 2 
1 2 3 | 1 2 0 | 1 3 0 | 2 0 1 | 2 1 0 | 2 0 3 | 2 3 0 | 2 3 1 | 2 1 3
            3 0 1 | 3 1 0 | 3 0 2 | 3 2 0 | 3 1 2 | 3 2 1

Is there a smooth way using boost/stl to achieve this?

Answer 1

LIVE DEMO

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

void dfs(int depth, int s, int i, std::vector<int>& c, const std::vector<int>& v)
{
    if (depth == s)
    {
        // base case: all chosen elements are in v, so we print
        //            all permutations of v
        do
        {
            std::copy(c.begin(), c.end(), std::ostream_iterator<int>(std::cout, " "));
            std::cout << "| ";
        }
        while (std::next_permutation(c.begin(), c.end()));
    }
    else
    {
        // regular case: loop and recurse, which effectively creates an
        //               n-dimensional for loop.
        //               This is the classic approach to finding the
        //               Cartesian product of N vectors or all combinations of elements.
        for (int j = i + 1; j < (int)v.size(); ++j)
        {
            c.push_back(v[j]);
            dfs(depth + 1, s, j, c, v);
            c.pop_back();
        }
    }
}

int main()
{
    std::vector<int> v{ 0, 1, 2, 3 };
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());    
    std::vector<int> c;
    const int length = 3;
    dfs(0, length, -1, c, v);
}

Output:

0 1 2 | 0 2 1 | 1 0 2 | 1 2 0 | 2 0 1 | 2 1 0 | 0 1 3 | 0 3 1 | 1 0 3 |
1 3 0 | 3 0 1 | 3 1 0 | 0 2 3 | 0 3 2 | 2 0 3 | 2 3 0 | 3 0 2 | 3 2 0 |
1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1