How to create permutations with replacement in C ++?

Question

Note. After reading the message templatetypedef it seems like I'm trying to calculate the Cartesian product of a set with me a certain number of times.

I'm not quite sure that the problem I'm trying to solve is being caused, but it seems pretty close to swapping with a replacement for me.

This is basically my problem. For an array, for example:

{1, 2, 3} 

and size, say 2. I need to output:

 {1,1},{1,2},{1,3},{2,1},{2,2},... 

If the size is 3, it will be

 {1,1,1},{1,1,2},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{1,3,1}... 

How can I do it?

For the purposes of my problem, I have an input size of 15 numbers, so I think I could create 15 for loops, but this seems like a hack to me.

Thanks.

Edit: I edited my problem without making sure what I asked and what I really need is essentially the same problem. After reading the templatetypedef post, it seems like I'm trying to calculate the Cartesian product of a set with the size itself once.

Answer 1

You are trying to calculate the Cartesian product of the set {1, 2, 3} with itself fifteen times. You can do this very elegantly with a simple recursive algorithm:

• To calculate the Cartesian product of a set with you only once, return a set containing singleton lists of each of the elements in the original set.
• To calculate the Cartesian product of a set with itself n> 1 times:
  • Recursively calculate the Cartesian product of a set with n - 1 times.
  • For each element x of the input list:
    • For each sequence S created so far:
      • Add the sequence S + x to the output set.
  • Returns the output set.

In the (somewhat inefficient) C ++ code:

 vector<vector<int>> CartesianPower(const vector<int>& input, unsigned k) { if (k == 1) { vector<vector<int>> result; for (int value: input) { result.push_back( {value} ); } return result; } else { vector<vector<int>> result; vector<vector<int>> smallerPower = CartesianProduct(input, k - 1); for (int elem: input) { for (vector<int> sublist: smallerPower) { sublist.push_back(elem); result.push_back(sublist); } } return result; } } 

Hope this helps!