如何在 Perl 中生成数组的所有排列? [英] How can I generate all permutations of an array in Perl?

问题描述

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

What's the best (elegant, simple, efficient) way to generate all n! permutations of an array in perl?

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

For example, if I have an array @arr = (0, 1, 2), I want to output all permutations:

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

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

It should probably be a function that returns an iterator (lazy/delayed evaluation because n! can become so impossibly large), so it can be called like this:

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

推荐答案

来自 perlfaq4:"我该怎么做置换列表的 N 个元素?":

在 CPAN 上使用 List::Permutor 模块.如果列表实际上是一个数组，请尝试 Algorithm::Permute 模块(也在 CPAN 上).它是用 XS 代码编写的，非常高效:

Use the List::Permutor module on CPAN. If the list is actually an array, try the Algorithm::Permute module (also on CPAN). It's written in XS code and is very efficient:

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

为了更快地执行，您可以这样做:

For even faster execution, you could do:

use Algorithm::Permute;

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

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

这是一个小程序，它生成每行输入上所有单词的所有排列.包含在 permute() 函数中的算法在 Knuth 的《计算机编程艺术》的第 4 卷(仍未出版)中进行了讨论，并且适用于任何列表:

Here's a little program that generates all permutations of all the words on each line of input. The algorithm embodied in the permute() function is discussed in Volume 4 (still unpublished) of Knuth's The Art of Computer Programming and will work on any list:

#!/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；否则返回下一个排列.

The Algorithm::Loops module also provides the NextPermute and NextPermuteNum functions which efficiently find all unique permutations of an array, even if it contains duplicate values, modifying it in-place: if its elements are in reverse-sorted order then the array is reversed, making it sorted, and it returns false; otherwise the next permutation is returned.

NextPermute 使用字符串顺序和 NextPermuteNum 数字顺序，因此您可以像这样枚举 0..9 的所有排列:

NextPermute uses string order and NextPermuteNum numeric order, so you can enumerate all the permutations of 0..9 like this:

use Algorithm::Loops qw(NextPermuteNum);

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

这篇关于如何在 Perl 中生成数组的所有排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！