在 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

我设置::双重交叉模块不正是你想要的东西。需要注意的是你是不是真正需要的排列，这是一组元素的顺序。你正在寻找的叉积，这是从不同组的元素的组合。

我的模块为您提供了一个迭代器，这样你就不会在内存中创建了这一切。您只需创建一个新的记录，当你需要它。

use Set::Crossproduct;

my $iterator = Set::CrossProduct->new(
    [
        [qw( foo bar baz )],
        [qw( cat dog     )],
        [qw( 1 2 3 4     )],
    ]
    );

while( my $tuple = $iterator->get ) {
    say join ' ', $tuple->@*;
    }

Answer 3

为列表的任意数量的简单递归溶液：

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

对于列表中的任意数A不那么简单的非递归溶液：

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 4

我首先想到的一种方法是使用几个 for 循环并且不使用递归。

1. 求排列总数
2. 从 0 循环到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 5

可以使用嵌套循环。

for my $e1 (qw( foo bar baz )) {
for my $e2 (qw( cat dog )) {
for my $e3 (qw( 1 2 3 4 )) {
   my @choice = ($e1, $e2, $e3); 
   ...
}}}

当你需要嵌套循环的任意数量的，可以使用算法::循环的NestedLoops。

use Algorithm::Loops qw( NestedLoops );

my @lists = (
   [qw( foo bar baz )],
   [qw( cat dog )],
   [qw( 1 2 3 4 )],
);

my $iter = NestedLoops(\@lists);
while ( my @choice = $iter->() ) {
   ...
}