Perlで配列のすべての順列を生成するにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/635768

質問

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";
}
役に立ちましたか？

解決

perlfaq4 を参照してください：＆quot;リストの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のThe Art of Computer ProgrammingのVolume 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";
}

Algorithm :: Permute と順列の繰り返し（Perl Journal、1998年秋）は興味深いあなたのために読んでください。

辞書順の順列を生成するアルゴリズムを見ることをお勧めします。 問題24 を最近解決した方法。配列内のアイテムの数が多くなると、後から順列を保存して並べ替えるのに費用がかかります。

Manniが提案した List :: Permutor のように見えますが、数値的に並べ替えられた順列を生成します。それが私がPerlを使用して行くことです。どうなったか教えてください。

Iterator :: Array :: Jagged をご覧ください。 。

これを試してください

use strict;
use warnings;

print "Enter the length of the string - ";
my $n = <> + 0;

my %hash = map { 
これを試してください



$ 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




出力：これは、数値の可能なすべての組み合わせを提供します。ロジックを追加して、不要な組み合わせを除外できます。


<*> => 1 } glob "{0,1,2}" x $n;

foreach my $key ( keys %hash ) {
    print "$key\n";
}

出力：これは、数値の可能なすべての組み合わせを提供します。ロジックを追加して、不要な組み合わせを除外できます。

<*>
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top