0: =pod What is a Cartesian Cross Product?
1: 
2: I think this is just too damn cool to pass up.  If you don't
3: know what a Cartesian (Cross-) Product is, it's basically:
4: 
5:   A = (1,2,3)
6:   B = (4,5)
7:   CCP(A,B) =>
8:    (1,4)
9:    (1,5)
10:    (2,4)
11:    (2,5)
12:    (3,4)
13:    (3,5)
14: 
15: Yay, that's all well and good.  Here's how to implement the
16: Cartesian Product generator in Perl:
17: 
18: =pod Explanation of algorithm used
19: 
20: Given a list of sets, say ([a,b], [c,d,e], [f,g]), we first determine how
21: many sets can be created.  Mathematically, this is determined as follows:
22: 
23:   For a list of sets, { a[1], a[2], ..., a[n] }, to determine how many sets
24:   can be created by choosing an element from a[1] as the first element of a
25:   set, an element of a[2] for the second element, and so on, picking an
26:   element of a[n] as the n-th element, we create a list { s[1], s[2], ...,
27:   s[n] }, where each element s[i] is the number of element in a[i].  We can
28:   pick any of the s[i] elements from a[i] for the specified element in the
29:   set to be created, so the number of sets to be created is
30: 
31:       n
32:     -----
33:      | |   s[p]  .
34:      | |
35:      p=1
36: 
37:   That is, the product of the sizes of all the sets.
38: 
39: Now that we know how many sets we'll be creating, we start to populate these
40: sets.  We modify the same index of each set per loop; that is, we modify
41: a[0][0], a[1][0], a[2][0], ..., a[n][0], before we modify any index in a[1].
42: 
43: I utilize a "repetition value", which starts at 1, and is multiplied by the
44: size of the previous set (s[i-1]) when the population of a specific index of
45: the new sets is complete.  The repetition value indicates how many times the
46: specific element will be inserted in a row on a pass over an index.  The
47: starting value of 1 means that each element in a[0] will be inserted once, and
48: then the next element will be entered, and after all elements have been
49: exhausted, we go back to inserting a[0].
50: 
51: After we've exhausted a[0], we multiply the repetition value by s[0], and we
52: move on to a[1].  For each value here, we fill in the next index in the new
53: sets, but we do this R times in succession, where R is the repetition value.
54: 
55: We continue through until the new sets are completed.
56: 
57: =cut
58: 
59:   sub cartesian {
60:     my $len = 1;
61:     my (@ret,$rep,$i,$j,$p,$k);
62: 
63:     for (@_) { $len *= @$_ }
64: 
65:     for ($rep = 1, $i = 0; $i < @_; $rep *= @{ $_[$i] }, $i++) {
66:       for ($j = 0, $p = 0; $j < $len; $j += $rep, $p++) {
67:         for ($k = 0; $k < $rep; $k++) {
68:           print STDERR << "DEBUGGING" if 0;  # set to true to see debug output
69: repetition value: $rep
70: modifying set[@{[ $j + $k]}], index[$i]
71: value is element @{[ $p % @{ $_[$i] } ]} ('$_[$i][$p % @{ $_[$i] }]') of original set[$i]
72: 
73: DEBUGGING
74:           $ret[$j + $k][$i] = $_[$i][$p % @{ $_[$i] }]
75:         }
76:       }
77:     }
78: 
79:     return @ret;
80:   }
81: 
82:   # uncomment to see a test run
83:   # print map "@$_\n", cartesian( [1,2] , [3,4,5] , [6,7] );