在Perl中，如何迭代多個集合的笛卡爾乘積？

鑑於x數組的數量，每個數組的數量可能不同，我如何遍歷所有組合，我從每個數組中選擇一個項目？在Perl中，如何迭代多個集合的笛卡爾乘積？

例子：

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

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

我這樣做在Perl，順便說一句。

來源

2009-08-10 erjiang

有不少關於計算器已經這個話題;只搜索「排列」。我沒有特別檢查是否有perl。 – balpha 2009-08-10 17:09:18

「排列」是一個錯誤的搜索，因爲這不是一個排列組合。 – 2010-07-05 07:23:00

遞歸和更流暢的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; 
}

來源

2009-08-10 18:31:43 erjiang

的列表任意數量的一個簡單的遞歸解決方案：

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

來源

2009-08-10 17:11:49 bdonlan

+1非常優雅，感謝分享 – dfa 2009-08-10 17:17:56

請注意，這裏有一些不必要的分配 - 它可以進一步優化。但這種一般方法是你想要的:) – bdonlan 2009-08-10 17:25:21

這不是你想要的方法。避免在Perl中遞歸，並且不要在內存中創建整個事物。 – 2009-08-10 18:11:27

還有一個方法，我首先想到使用一對夫婦的循環和沒有遞歸。

找到排列的總數
環路total_permutations-1
觀察到，通過利用循環索引模數元素的數目在一個陣列，可以得到每一個排列

實施例：

鑑於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 ...]，並且可以記憶一小部分。當然，遞歸更簡潔，但這對於遞歸受堆棧大小嚴重限制的語言可能很有用。

來源

2009-08-10 17:58:58 erjiang

我認爲它和三個嵌套循環一樣，除了這個方法你也花時間在這個過程中做數學。 – 2009-08-10 18:30:25

循環三元組效率高且易於閱讀 – dfa 2009-08-10 18:32:46

只需少量工作，此方法可用於任何數量的列表，這對嵌套for循環無法說明。 – barrycarter 2014-05-10 01:43:10

我的Set::CrossProduct模塊正是你想要的。請注意，你並不是真的在尋找排列，這是排列中的元素排序。您正在尋找交叉產品，這是來自不同組合的元素的組合。

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

來源

2009-08-10 18:08:23

+1 ...我沒有看到你的帖子，當我嘗試重複這個模塊的功能時（我也不知道它是否存在）。 – 2009-08-10 18:52:48

在Perl中，如何迭代多個集合的笛卡爾乘積？

回答

相關問題