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

Question

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

例如,如果我有一个数组@arr = (0, 1, 2),我想输出所有排列:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

它应该是一个返回迭代器的函数(延迟/延迟评估,因为它n!可能变得非常大),所以它可以这样调用:

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

Answer 1

我建议你使用List :: Permutor:

use List::Permutor;

my $permutor = List::Permutor->new( 0, 1, 2);
while ( my @permutation = $permutor->next() ) {
    print "@permutation\n";
}

Answer 2

请参阅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;

这是一个小程序,它生成每行输入中所有单词的所有排列.在Knuth的计算机编程艺术的第4卷(尚未发表)中讨论了permute()函数中包含的算法,该算法可以在任何列表中使用:

#!/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;

Answer 3

你可以使用Algorithm :: Permute和Iterating Over Permutations(Perl Journal,1998年秋季)对你来说很有意思.