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

Question

我想用 Perl 进行排列。例如，我有三个数组： ["big", "tiny", "small"] 然后我有 ["red", "yellow", "green"] 以及[“苹果”、“梨”、“香蕉”]。

我如何得到：

["big", "red", "apple"]
["big", "red", "pear"]

..etc..

["small", "green", "banana"]

我知道这叫做排列。但我不知道该怎么做。我也不知道我可以有多少个数组。可能有三四个，所以我不想做嵌套循环。

Answer 1

这实际上不是排列，而是笛卡尔积。请参阅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
big red apple
big red pear
big red banana
big yellow apple
big yellow pear
big yellow banana
big green apple
big green pear
big green banana
tiny red apple
tiny red pear
tiny red banana
tiny yellow apple
tiny yellow pear
tiny yellow banana
tiny green apple
tiny green pear
tiny green banana
small red apple
small red pear
small red banana
small yellow apple
small yellow pear
small yellow banana
small green apple
small green pear
small green banana

Answer 2

现在以 twitter 形式：

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

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

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

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] 的数组的引用。

然后，外部映射的主体运行三次，将 $_ 设置为 [1]，然后是 [2]，最后是 [3]。然后，对于外部映射的每次迭代，内部映射都会在 (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 上发布了一个问题，要求有人向我解释这一点。

您可以轻松地根据您的问题调整此解决方案。

Answer 4

如果您愿意，可以使用我的 Set::CrossProduct 模块。您不必遍历整个空间，因为它为您提供了一个迭代器，因此您可以控制一切。

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

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"]);