1

EDIT

Just found another thread on SO that's pretty much exactly what I needed: How can I create cartesian product of vector of vectors?

Thanks everyone!

Let's say I have one set of values S1(A, B, C) and another, S2(D, E, F), where a transformation S1 -> S2 will give another set, S3, where S3(AD, AE, AF, BD, BE, BF, CD, CE, CF); in other words, I'd like to map each value of the first set to each value of the second set, thus getting a third set that has a size of S1 x S1.

Now, doing this for two sets is a trivial matter, however, I am at a loss when it comes to have a variable number of sets, i.e. S1 -> S2 -> S3 -> ... -> Sn

If we view this as a tree/graph structure, the problem is solved by finding every single path:

        start
          .
    .     .     .
   A      B      C
   .      .      .
 . . .  . . .  . . .
 D E F  D E F  D E F

Is there a scalable algorithm to solve this problem?

Community
  • 1
  • 1
stellarossa
  • 1,730
  • 1
  • 18
  • 29
  • 1
    Check out [Cartesian Product](http://en.wikipedia.org/wiki/Cartesian_product). I know some languages have this built-in. For example, Python has `itertools.product(*iterables)` – Kevin Dec 12 '13 at 18:54
  • @Kevin actually stumbled upon it [just 2 minutes ago](http://en.wikipedia.org/wiki/Projection_%28set_theory%29); unfortunately, i don't think C++ has this. – stellarossa Dec 12 '13 at 18:55
  • 1
    Google n-ary cartesian product. There're many variations, but all have O(n^2) complexity. – Dan Kruchinin Dec 12 '13 at 18:57

1 Answers1

2

This, by definition, would be recursion. If you put all of these sets into a multi-dimensional array you could easily recurse through all of the different levels and create your final set.

Kirkland
  • 3,257
  • 1
  • 16
  • 17
  • 1
    What Kirkland means is that, in general, tree-like structures can be traversed with a recursive algorithm, where you treat each node of the tree (except for the leaf ones) as its own tree. Of course, without a code example, that's pretty hard to visualize. – Robert Harvey Dec 12 '13 at 18:53