4

Note:After reading templatetypedef's post, it seems like I'm trying to compute the cartesian product of a set with itself a certain amount of times.

I am not completely sure what the problem I'm trying to solve is called, but it seems pretty close to permutation with replacement to me.

So basically, my problem is this. Given an array, for example:

{1, 2, 3}

and a size, say 2. I need to output:

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

If size was 3, then it would be 

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

How would I do this?

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

Thanks.

Edit: I edited my problem after becoming not sure what I was asking and what I actually needed were essentially the same problem. After reading templatetypedef's post, it seems like i'm trying to compute the cartesian product of a set with itself size amount of times.

Improve this question

1 Answer 1

Reset to default
3

You are trying to compute 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 compute the Cartesian product of a set with itself just once, return a set containing singleton lists of each of the elements of the original set.
  • To compute the Cartesian product of a set with itself n > 1 times:
    • Recursively compute the Cartesian product of the set with itself n - 1 times.
    • For each element x of the input list:
      • For each sequence S produced so far:
        • Add the sequence S + x to the output set.
    • Return the output set.

In (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!

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

What does for(int elem: input) do? Are you trying to iterate through input and assign the value to elem?
@horacehe- This is the C++11 range-based for loop. It means "iterate across the elements of input, at each stage setting elem equal to the current element of input."
When I try to run it, it gives an error, saying error: expected initializer before ':' token. I'm editing it to workaround it, so don't worry about that.
@horacehe- You need a C++11 compiler in order to get this code to work. You might need to explicitly enable this in your build settings / on the command-line.
Another thing that I'm having trouble with. How does sublist push back input if input isn't an int?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.