All Permutations of Elements in a 2D Vector (Cartesian Product)

Question

This is a small part that I've been stuck on, and it's part of a much larger assignment.

I have a 2D vector such as:

v1: 0 1 2 3 4  
v2: 0 1 2  
v3: 0 1 2 3 4  
v4: 0 1 2 3  
v5: 0 1 2 3 4

(each row is a vector)

I need to find all the permutations, choosing one element from each row. As someone pointed out, this would be the cartesian product.
I tried using loops, but that will only work in one direction (it misses quite a few permutations)
I also looked into next_permutation, but I'm not sure if it's possible to apply this to a 2D vector.

Additionally, the number of rows is not static, so I cannot nest 5 loops, as there could be more or less rows depending on the conditions.

Is there a way to do this?

possible duplicate of [Perfoming Cartesian product on arrays](http://stackoverflow.com/questions/10840430/perfoming-cartesian-product-on-arrays) — templatetypedef, Jun 18 '12 at 22:04
What you are looking for is not subsets, but the Cartesian product (all ways of picking one element out of each). — templatetypedef, Jun 18 '12 at 22:04

score 2 · Accepted Answer · answered Jun 18 '12 at 22:18

I'm going to just write out one possible answer, which is not terribly efficient, but should be useable.

Note that I'm assuming that (in your example) you want all 5-element groups, with first element taken from v1, second element taken from v2, third from v3, etc.

void gen_all (
    vector<vector<int> > & output_perms,
    vector<vector<int> > const & input,
    vector<int> & cur_perm,
    unsigned cur_row = 0
)
{
  if (cur_row >= input.size())
  {
    // This is where you have found a new permutation.
    // Do whatever you want with it.
    output_perms.push_back (cur_perm);
    return;
  }

  for (unsigned i = 0; i < input[cur_row].size(); ++i)
  {
    cur_perm.push_back (input[cur_row][i]);
    gen_all (output_perms, input, cur_perm, cur_row + 1);
    cur_perm.pop_back ();
  }
}

Call the above function like this: (assuming v holds your original sets.)

vector<vector<int> > output;
vector<int> temp;
gen_all (output, v, temp);

As I said before, there are much more efficient and elegant ways, and the above code might not even compile (I just wrote it here.)

This question is tagged `homework`. Does that mean I shouldn't have posted a solution in code?! — yzt, Jun 18 '12 at 22:45
I actually did find a recursive cartesian product function posted on here which gave me a good place to look. Unfortunately it turns out that my entire way of looking at the problem was inefficient, and I should have been using backtracking. Thanks for the solution though, it's quite a bit easier to understand than some of the other attempts. — SamTheSammich, Jun 19 '12 at 15:50

score 1 · Answer 2 · answered Jun 18 '12 at 22:11

std::next_permutation only works on one set of iterators. It doesn't keep any static memory though, it is all based on the current state of the iterators. That means you can use it on more than one vector at a time. Don't try to permute the whole structure at once.

All Permutations of Elements in a 2D Vector (Cartesian Product)

2 Answers2