在Perl中，如何迭代多个集合的笛卡尔乘积？

Question

鉴于x数组的数量，每个数组的数量可能不同，我如何遍历所有组合，我从每个数组中选择一个项目？

例子：

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

返回

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

我这样做在Perl，顺便说一句。

Answer 1

递归和更流畅的Perl的例子（有解说和文档）做笛卡尔乘积可以在http://www.perlmonks.org/?node_id=7366找到

例子：

sub cartesian { 
    my @C = map { [ $_ ] } @{ shift @_ }; 

    foreach (@_) { 
     my @A = @$_; 

     @C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A; 
    } 

    return @C; 
} 

Answer 2

的列表任意数量的一个简单的递归解决方案：

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; 
} 

一个不那么简单的非递归解决方案列表任意数量：

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"; 
} 

Answer 3

还有一个方法，我首先想到使用一对夫妇的循环和没有递归。

1. 找到排列的总数
从0
2. 环路total_permutations-1
3. 观察到，通过利用循环索引模数元素的数目在一个阵列，可以得到每一个排列

实施例：

鉴于A [3]，B [2]，C [3]，

for (index = 0..totalpermutations) { 
    print A[index % 3]; 
    print B[(index/3) % 2]; 
    print C[(index/6) % 3]; 
} 

当然可以用for循环代替循环[A B C ...]，并且可以记忆一小部分。当然，递归更简洁，但这对于递归受堆栈大小严重限制的语言可能很有用。

Answer 4

我的Set::CrossProduct模块正是你想要的。请注意，你并不是真的在寻找排列，这是排列中的元素排序。您正在寻找交叉产品，这是来自不同组合的元素的组合。

我的模块给你一个迭代器，所以你不会在内存中创建它。只有在需要时才创建一个新的元组。