どのようにしてPerlで配列のすべての順列を生成できますか？

Question

Perlで配列のすべてのn!順列を生成するには、（エレガントでシンプルな、効率的な）最良の方法はありますか？例えば

私は配列@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

はperlfaq4を参照してください："How do I permute N elements of a list?"

---

使用リスト:: CPANにPermutorモジュール。リストが実際に配列の場合は、Algorithm :: Permuteモジュール（CPANでも可能）を試してみてください。

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

より速く実行するために、あなたができる：それはXSコードで書かれており、非常に効率的であるのです

use Algorithm::Permute; 

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

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

は、ここで入力の各ライン上のすべての単語のすべての順列を生成し、小さなプログラムです。並び替える（）関数の中で具現化アルゴリズムは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; 

アルゴリズム::ループモジュールはまた、NextPermuteを提供し、 NextPermuteNumは、重複した値が含まれていても、配列のすべてのユニークな順列を効率的に検索し、インプレースで修正します。そうでなければ、次の置換が返される。

あなたはこのような0..9のすべての順列を列挙することができるようにNextPermuteは、文字列の順序とNextPermuteNum数値順を使用しています：

use Algorithm::Loops qw(NextPermuteNum); 

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

Answer 2

あなたはAlgorithm::Permuteと多分Iterating Over Permutationsは（Perlのジャーナルは、1998年秋）あなたのための興味深い読み取りで使用することができます。

Answer 3

私はあなたがList::Permutorを使用することをお勧め：

use List::Permutor; 

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

Answer 4

はIterator::Array::Jaggedを見てみましょう。

Answer 5

自分で書きたい場合は、再帰アルゴリズムs.t.それは配列から1つの項目を取り出し、配列がサイズ1になるまで、より小さな配列でそれ自身を呼び出します。

非常にきれいでなければなりません。

Answer 6

私はを最近解決した方法であるalgorithm for generating permutations in lexicographical orderを見ることをお勧めします。配列内の項目の数が大きくなると、あとで順列を格納しソートするのに費用がかかります。

Manniによって提案されたList::Permutorのように、数値的にソートされた順列が生成されます。それは私がPerlを使って行くことです。それがどのように判明したか教えてください。

Answer 7

Perlmonksは、いくつかの例があります：http://www.perlmonks.org/?node_id=503904

Answer 8

出力

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