如何在Perl中生成数组的所有排列？

一尘不染

如何在Perl中生成数组的所有排列？

algorithm

n!在perl中生成数组的所有排列的最佳（优雅，简单，高效）方法是什么？

例如，如果我有一个array @arr = (0, 1, 2)，我想输出所有排列：

它可能应该是一个返回迭代器的函数（延迟/延迟评估，因为它n!可能变得如此之大），因此可以这样调用它：

my @arr = (0, 1, 2);
my $iter = getPermIter(@arr);
while (my @perm = $iter->next() ){
    print "@perm\n";
}

阅读 367

2020-07-28

共1个答案

一尘不染

来自perlfaq4：“如何置换列表的N个元素？”
：

使用CPAN上的List :: Permutor模块。如果列表实际上是一个数组，请尝试Algorithm ::
Permute模块（同样在CPAN上）。它是用XS代码编写的，非常有效：

use Algorithm::Permute;

my @array = 'a'..'d';
my $p_iterator = Algorithm::Permute->new ( \@array );

while (my @perm = $p_iterator->next) {
   print "next permutation: (@perm)\n";
}

为了更快地执行，您可以执行以下操作：

use Algorithm::Permute;

my @array = 'a'..'d';

Algorithm::Permute::permute {
    print "next permutation: (@array)\n";
} @array;

这是一个小程序，在输入的每一行上生成所有单词的所有排列。permute（）函数中包含的算法在Knuth的《计算机编程的艺术》的第4卷（尚未出版）中进行了讨论，并且可以在任何列表上使用：

#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator

sub permute (&@) {
    my $code = shift;
    my @idx = 0..$#_;
    while ( $code->(@_[@idx]) ) {
        my $p = $#idx;
        --$p while $idx[$p-1] > $idx[$p];
        my $q = $p or return;
        push @idx, reverse splice @idx, $p;
        ++$q while $idx[$p-1] > $idx[$q];
        @idx[$p-1,$q]=@idx[$q,$p-1];
    }
}


permute { print "@_\n" } split;

Algorithm ::
Loops模块还提供了NextPermute和NextPermuteNum函数，这些函数可以有效地查找数组的所有唯一排列，即使它包含重复值也可以对其进行就地修改：如果其元素按相反的顺序排列，则该数组将被反向，使其排序，并返回false；否则，返回下一个排列。

NextPermute使用字符串顺序和NextPermuteNum数字顺序，因此您可以枚举0..9的所有排列，如下所示：

use Algorithm::Loops qw(NextPermuteNum);

my @list= 0..9;
do { print "@list\n" } while NextPermuteNum @list;

2020-07-28