在Perl中，我如何得到多个集合的笛卡尔积？

Question

我想在Perl中进行排列组合。例如，我有三个数组：["big", "tiny", "small"]，然后是["red", "yellow", "green"]，以及["apple", "pear", "banana"]。

我该如何得到：

["big", "red", "apple"]
["big", "red", "pear"]
..等等..
["small", "green", "banana"]

我了解这被称为排列组合。但我不知道如何做。而且我不知道我可以有多少个数组。可能有三个或四个，所以我不想使用嵌套循环。

- user295033

---

这不是排列 - 排列是给定集合的排序（例如 {a,b,c} -> (a,b,c), (a,c,b), (b,a,c), ...）。 - Cascabel

哦，抱歉。我不知道。是组合吗？ - user295033

实际上，我刚注意到这是一个重复的问题：请参见https://dev59.com/PEjSa4cB1Zd3GeqPItPV - Sinan Ünür

@nubie2 请查看 http://en.wikipedia.org/wiki/Permutation 和 http://en.wikipedia.org/wiki/Combination。 - Sinan Ünür

我没有在那个重复的内容中看到关于 Math::Cartesian::Product 的提及。 - Cascabel

@Jefromi，但是那里得票最高的答案可能根据数组的基数而有更好的选择。 - Sinan Ünür

Answer 1

其实这不是排列(permutation)，而是笛卡尔积(Cartesian product)。请查看Math::Cartesian::Product。

#!/usr/bin/perl

use strict; use warnings;

use Math::Cartesian::Product;

cartesian { print "@_\n" }
    ["big", "tiny", "small"],
    ["red", "yellow", "green"],
    ["apple", "pear", "banana"];

输出：

C:\Temp> uu
大红苹果
大红梨
大红香蕉
大黄苹果
大黄梨
大黄香蕉
大绿苹果
大绿梨
大绿香蕉
小红苹果
小红梨
小红香蕉
小黄苹果
小黄梨
小黄香蕉
小绿苹果
小绿梨
小绿香蕉
微小红苹果
微小红梨
微小红香蕉
微小黄苹果
微小黄梨
微小黄香蕉
微小绿苹果
微小绿梨
微小绿香蕉
小小红苹果
小小红梨
小小红香蕉
小小黄苹果
小小黄梨
小小黄香蕉
小小绿苹果
小小绿梨
小小绿香蕉

- Sinan Ünür

---

哦天啊，我完全不知道。这会让我省去很多麻烦！ - Vivin Paliath

小提示：Math::Cartesian::Product使你立即遍历整个空间。这可能是你想要的。如果你想反转控制，请使用Set::CrossProduct。 - brian d foy

Answer 2

现在是twitter格式：

sub prod { reduce { [ map { my $i = $_; map [ @$_, $i ], @$a } @$b ] } [[]], @_ }

这段话涉及到IT技术。

use strict;
use warnings;
use List::Util qw(reduce);

sub cartesian_product {
  reduce {
    [ map {
      my $item = $_;
      map [ @$_, $item ], @$a
    } @$b ]
  } [[]], @_
}

- hobbs

---

@nubie2 基本上与 Vivin Paliath 的解决方案相同，只是使用了 reduce 而非递归。从一个 0-元组的列表（[[]]）开始，然后对于输入中的每个数组引用，将每个项附加到现有条目的每个条目。如果您知道 reduce 的作用，很容易在纸上跟踪出来。如果您不知道 reduce 的作用，请学习！ :) - hobbs

s/solution that/solution posted by/ - hobbs

非常好的答案，谢谢！使用 map [ $item, @$_ ] 可以改变输出顺序，使其与通过一系列嵌套循环生成笛卡尔积时的顺序相匹配，其中最外层循环控制最左边的输出数组元素。这对我来说更自然。 - ggorlen

Answer 3

几年前，我也遇到过这个问题。我没有能够提出自己的解决方案，但是我找到了这段精妙而明智地使用了map和递归的代码：

#!/usr/bin/perl

print "permute:\n";
print "[", join(", ", @$_), "]\n" for permute([1,2,3], [4,5,6], [7,8,9]);

sub permute {

    my $last = pop @_;

    unless(@_) {
           return map([$_], @$last);
    }

    return map { 
                 my $left = $_; 
                 map([@$left, $_], @$last)
               } 
               permute(@_);
}

是的，这看起来很疯狂，但请允许我解释一下！该函数将递归调用直到@_为空，此时它会将([1]，[2]，[3])（三个数组引用的列表）返回给上一级递归。在那个级别上，$last是一个包含[4, 5, 6]的数组的引用。

然后，外部map的主体运行三次，其中$_分别设置为[1]，[2]和[3]。内部map随后在每次外部map的迭代中对(4, 5, 6)进行运行，并返回([1, 4]，[1, 5]，[1, 6])，([2, 4]，[2, 5]，[2, 6])，最后是([3, 4]，[3, 5]，[3, 6])。

倒数第二个递归调用然后返回([1, 4]，[1, 5]，[1, 6]，[2, 4]，[2, 5]，[2, 6]，[3, 4]，[3, 5]，[3, 6])。

然后，它将该结果与[7,8,9]一起运行，这将给出[1, 4, 7]，[1, 4, 8]，[1, 4, 9]，[1, 5, 7]，[1, 5, 8]，[1, 5, 9]，[1, 6, 7]，[1, 6, 8]，[1, 6, 9]，[2, 4, 7]，[2, 4, 8]，[2, 4, 9]，[2, 5, 7]，[2, 5, 8]，[2, 5, 9]，[2, 6, 7]，[2, 6, 8]，[2, 6, 9]，[3, 4, 7]，[3, 4, 8]，[3, 4, 9]，[3, 5, 7]，[3, 5, 8]，[3, 5, 9]，[3, 6, 7]，[3, 6, 8]，[3, 6, 9] 我记得在perlmonks.org上发布了一个问题，要求有人解释这个。

您可以轻松地将此解决方案适应于您的问题。

- Vivin Paliath

---

谢谢你的解决方案，但我认为Sinan的解决方案更简单。不过还是感谢你解释你的解决方案。 - user295033

没问题！我也喜欢Sinan的解决方案。简单多了！ - Vivin Paliath

Answer 4

如果您愿意，可以使用我的Set::CrossProduct模块。它提供了一个迭代器，因此您无需遍历整个空间，而是可以自行控制。

- brian d foy

Answer 5

如果

• 您不想包含依赖项
• 您只有少量的数组
• 您的数组不是非常巨大

那么 您可以简单地执行以下操作:

对于两个数组@xs和@ys：

map{ my $x = $_; map { [$x, $_] } @ys } @xs

对于三个数组 @xs、@ys、@zs。

map{ my $x = $_; map { my $y = $_; map { [$x, $y, $_] } @zs } @ys } @xs

- Dacav

Answer 6

这是我的解决方案，不需要任何模块，并且可以处理任意数量的集合。

sub set_product {
    my @array_of_aref = @_;
    if (@array_of_aref == 0) {
        return;
    }
    elsif (@array_of_aref == 1) {
        return $array_of_aref[0];
    }
    elsif (@array_of_aref >= 2) {
        my $array_a = shift @array_of_aref;
        my $array_b = shift @array_of_aref;
        my @array_c;
        foreach my $a ($array_a->@*) {
            foreach my $b ($array_b->@*) {
                if (ref $a eq "" and ref $b eq "") {
                    push @array_c, [$a,     $b];
                }
                elsif (ref $a eq "ARRAY" and ref $b eq "") {
                    push @array_c, [$a->@*, $b];
                }
                elsif (ref $a eq "" and ref $b eq "ARRAY") {
                    push @array_c, [$a,     $b->@*];
                }
                elsif (ref $a eq "ARRAY" and ref $b eq "ARRAY") {
                    push @array_c, [$a->@*, $b->@*];
                }
            }
        }
        while (my $aref = shift @array_of_aref) {
            @array_c = set_product(\@array_c, $aref);
        }
        return @array_c;
    }
}

示例：

    print $_->@* foreach set_product(["a","b"]);
    print $_->@* foreach set_product(["a","b"], [1,2,3]);
    print $_->@* foreach set_product(["a","b"], [1,2,3], ["x","y"]);
    print $_->@* foreach set_product(["a","b"], [1,2,3], ["x","y"], ["E","F"]);

- WhiteMist