如何在Perl中生成数组的所有排列?
-
10-07-2019 - |
题
在perl中生成数组的所有n!
排列的最佳(优雅,简单,高效)方法是什么?
例如,如果我有一个数组@arr = (0, 1, 2)
,我想输出所有排列:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
它应该是一个返回迭代器的函数(延迟/延迟评估,因为<=>可能变得如此不可思议的大),所以它可以这样调用:
my @arr = (0, 1, 2);
my $iter = getPermIter(@arr);
while (my @perm = $iter->next() ){
print "@perm\n";
}
解决方案
请参阅 perlfaq4 : <!>”我如何置换列表中的N个元素?<!> QUOT;
在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;
这是一个小程序,它可以生成每行输入中所有单词的所有排列。 peruth()函数中包含的算法在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;
其他提示
我建议您使用 List :: Permutor :
use List::Permutor;
my $permutor = List::Permutor->new( 0, 1, 2);
while ( my @permutation = $permutor->next() ) {
print "@permutation\n";
}
你可以使用算法:: Permute ,也许迭代排列(Perl Journal,1998年秋季)是一个有趣的为你读。
试试这个,
use strict;
use warnings;
print "Enter the length of the string - ";
my $n = <> + 0;
my %hash = map { $_ => 1 } glob "{0,1,2}" x $n;
foreach my $key ( keys %hash ) {
print "$key\n";
}
输出:这将给出所有可能的数字组合。您可以添加逻辑来过滤掉不需要的组合。
$ perl permute_perl.pl
Enter the length of the string - 3
101
221
211
100
001
202
022
021
122
201
002
212
011
121
010
102
210
012
020
111
120
222
112
220
000
200
110
不隶属于 StackOverflow