在Perl中,我如何获得多组笛卡尔积？

Question

我想在Perl中进行排列.例如,我有三个数组:["big", "tiny", "small"]然后我有["red", "yellow", "green"],也有["apple", "pear", "banana"].

如何得到:

["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

几年前我不得不解决这个问题.我无法提出自己的解决方案,而是遇到了这段精彩的代码,其中包括巧妙和明智地使用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])(三个arrayrefs的列表)到前一级递归.在该级别$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 3

现在以推特形式:

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

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

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

Answer 4

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