Wie kann ich alle Permutationen eines Arrays in Perl generieren?

Question

Was ist die beste (elegante, einfache, effiziente) Möglichkeit, alle n! Permutationen eines Arrays in Perl zu generieren?

Zum Beispiel, wenn ich ein Array haben @arr = (0, 1, 2), möchte ich die Ausgabe alle Permutationen:

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

Es sollte wohl eine Funktion sein, die einen Iterator zurückgibt (lazy/verzögerte Auswertung weil n! kann so unglaublich groß werden), so kann es wie folgt aufgerufen werden:

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

Answer 1

Siehe perlfaq4: "How do I permute N elements of a list?"

---

Verwenden Sie die Liste :: Permutor Modul auf CPAN. Wenn die Liste tatsächlich ein Array ist, versuchen Sie das Algorithm :: Permute-Modul (auch auf CPAN). Es geschrieben in XS-Code und ist sehr effizient:

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

Für eine noch schnellere Ausführung, könnten Sie tun:

use Algorithm::Permute; 

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

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

Hier ist ein kleines Programm, das auf jeder Zeile der Eingabe alle Permutationen aller Wörter erzeugt . Der Algorithmus in der permute() Funktion ausgeführt ist in Band 4 (noch nicht veröffentlichten) von Knuth The Art of Computer Programming diskutiert und wird auf jeder Liste arbeiten:

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

Der Algorithmus :: Loops Modul bietet auch die NextPermute und NextPermuteNum-Funktionen, die effizient alle eindeutigen Permutationen eines Arrays finden, selbst wenn sie doppelte Werte enthalten, und diese direkt ändern: Wenn ihre Elemente in umgekehrter Reihenfolge angeordnet sind, wird das Array umgekehrt und sortiert und gibt false zurück; Andernfalls wird die nächste Permutation zurückgegeben.

NextPermute verwendet String um und NextPermuteNum numerischer Reihenfolge, so können Sie alle Permutationen von 0..9 wie folgt aufzählen:

use Algorithm::Loops qw(NextPermuteNum); 

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

Answer 2

könnten Sie verwenden Algorithm::Permute und vielleicht Iterating Over Permutations (The Perl Journal, Herbst 1998) für Sie eine interessante Lektüre ist.

Answer 3

Ich schlage vor, Sie List::Permutor verwenden:

use List::Permutor; 

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

Answer 4

einen Blick auf Iterator::Array::Jagged nehmen.

Answer 5

Wenn Sie Ihre eigenen schreiben wollen, ein rekursiver Algorithmus s.t. es würde ein Element aus dem Array auswählen und den Aufruf mit dem kleineren Array an sich selbst vornehmen, bis das Array die Größe eins hat.

Es sollte ziemlich sauber sein.

Answer 6

Ich empfehle ein Blick auf eine algorithm for generating permutations in lexicographical order, die ich vor kurzem Problem 24 gelöst hat. Wenn die Anzahl der Elemente in dem Array groß wird, wird es teuer, später Permutationen zu speichern und zu sortieren.

Es sieht aus wie List::Permutor, die von Manni vorgeschlagen wurde, generiert numerisch sortierte Permutationen. Das würde ich mit Perl machen. Lassen Sie uns wissen, wie es sich entwickelt.

Answer 7

PerlMonks hat einige Beispiele: http://www.perlmonks.org/?node_id=503904

Answer 8

die Sie interessieren,

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

Ausgang: Dies gibt die alle möglichen Kombinationen der Zahlen. Sie können die Logik hinzufügen, um die unerwünschten Kombinationen herauszufiltern.

$ 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