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.
A simple recursive solution for an arbitrary number of lists:
sub permute {
my ($first_list, @remain) = @_;
unless (defined($first_list)) {
return []; # only possibility is the null set
}
my @accum;
for my $elem (@$first_list) {
push @accum, (map { [$elem, @$_] } permute(@remain));
}
return @accum;
}
A not-so-simple non-recursive solution for an arbitrary number of lists:
sub make_generator {
my @lists = reverse @_;
my @state = map { 0 } @lists;
return sub {
my $i = 0;
return undef unless defined $state[0];
while ($i < @lists) {
$state[$i]++;
last if $state[$i] < scalar @{$lists[$i]};
$state[$i] = 0;
$i++;
}
if ($i >= @state) {
## Sabotage things so we don't produce any more values
$state[0] = undef;
return undef;
}
my @out;
for (0..$#state) {
push @out, $lists[$_][$state[$_]];
}
return [reverse @out];
};
}
my $gen = make_generator([qw/foo bar baz/], [qw/cat dog/], [1..4]);
while ($_ = $gen->()) {
print join(", ", @$_), "\n";
}
There's one method I thought of first that uses a couple for loops and no recursion.
Example:
Given A[3], B[2], C[3],
for (index = 0..totalpermutations) {
print A[index % 3];
print B[(index / 3) % 2];
print C[(index / 6) % 3];
}
where of course a for loop can be substituted to loop over [A B C ...], and a small part can be memoized. Of course, recursion is neater, but this might be useful for languages in which recursion is severely limited by stack size.
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.
Recursive and more-fluent Perl examples (with commentary and documentation) for doing the Cartesian product can be found at http://www.perlmonks.org/?node_id=7366
Example:
sub cartesian {
my @C = map { [ $_ ] } @{ shift @_ };
foreach (@_) {
my @A = @$_;
@C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A;
}
return @C;
}
Here is something that seems to work for some definition of "work". It is very likely to be slower than the nested loops, but I have not done any measurement.
#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( max );
my @arrays = (
[ qw( foo bar baz) ],
[ qw( cat dog ) ],
[ 1, 2, 3, 4 ],
);
my $count = 1;
$count *= @{ $_ } for @arrays;
my $max = max map { scalar @{ $_} } @arrays;
my @generators = map { generate( $_, $max ) } @arrays;
my @output;
for ( 1 .. $count ) {
print join($", map { $_->() } @generators), "\n";
}
sub generate {
my @array = @{ shift @_ };
my $max = shift;
my $index = 0;
if ( $max == @array ) {
return sub { $array[ $index++ % @array ] };
}
else {
my $this = -1;
return sub {
unless ( ++$this < $max ) {
$this = 0;
$index += 1;
}
return $array[ $index % @array ];
};
}
}
Output:
C:\Temp> fgh foo cat 1 foo cat 2 foo cat 3 foo cat 4 bar dog 1 bar dog 2 bar dog 3 bar dog 4 baz cat 1 baz cat 2 baz cat 3 baz cat 4 foo dog 1 foo dog 2 foo dog 3 foo dog 4 bar cat 1 bar cat 2 bar cat 3 bar cat 4 baz dog 1 baz dog 2 baz dog 3 baz dog 4