algorithm - In Perl, how can I iterate over the Cartesian product of multiple sets?

Question

Given x number of arrays, each with a possibly different number of elements, how can I iterate through all combinations where I select one item from each array?

Example:

[   ]   [   ]   [   ]
 foo     cat      1
 bar     dog      2
 baz              3
                  4

Returns

[foo]   [cat]   [ 1 ]
[foo]   [cat]   [ 2 ]
  ...
[baz]   [dog]   [ 4 ]

I'm doing this in Perl, btw.

Answer 1

My Set::CrossProduct module does exactly what you want. Note that you aren't really looking for permutations, which is the ordering of the elements in a set. You're looking for the cross product, which is the combinations of elements from different sets.

My module gives you an iterator, so you don't create it all in memory. You create a new tuple only when you need it.

use Set::Crossproduct;

my $iterator = Set::CrossProduct->new(
    [
        [qw( foo bar baz )],
        [qw( cat dog     )],
        [qw( 1 2 3 4     )],
    ]
    );

while( my $tuple = $iterator->get ) {
    say join ' ', $tuple->@*;
    }