在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模塊正是你想要的。請注意，你並不是真的在尋找排列，這是排列中的元素排序。您正在尋找交叉產品，這是來自不同組合的元素的組合。

我的模塊給你一個迭代器，所以你不會在內存中創建它。只有在需要時才創建一個新的元組。