Wie kann ich alle Permutationen eines Arrays in Perl generieren?

Question

Was ist die beste (elegant, einfach, effizient) Art und Weise alle n! Permutationen eines Arrays in Perl zu generieren?

Zum Beispiel, wenn ich ein Array @arr = (0, 1, 2) haben, 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! so unglaublich groß werden kann), 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 : "Wie permutieren I N Elemente einer Liste?"

---

Mit der Liste :: Permutor Modul auf CPAN. Wenn die Liste tatsächlich ein Array ist, versuchen, den Algorithmus :: Vertausche Modul (auch auf CPAN). Es ist in XS-Code geschrieben 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 alle Permutationen aller Worte auf jeder Zeile der Eingabe erzeugt. Der Algorithmus in der permute () Funktion ausgeführt ist in Band 4 (noch nicht veröffentlicht) 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, auch wenn es doppelte Werte enthält, ist es an Ort und Stelle ändern: wenn ihre Elemente in umgekehrter Reihenfolge sortiert werden dann die Anordnung umgekehrt wird, sie sortiert zu machen, und es kehrt false; sonst wird die nächste Permutation zurückgeführt wird.

NextPermute verwendet Zeichenfolge 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

Ich schlage vor, Sie verwenden Liste :: Permutor :

use List::Permutor;

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

Answer 3

könnten Sie Algorithm :: Vertausche und vielleicht Iterieren über Permutationen (The Perl Journal, Herbst 1998) ist ein interessanter lesen für Sie.

Answer 4

Ich empfehle auf einem Algorithmus für Permutationen in lexikographische Ordnung Erzeugung, das ist wie ich vor kurzem Problem 24 gelöst. Wenn die Anzahl der Elemente im Array groß wächst, wird es teuer Permutationen zu speichern und sortieren später.

Es sieht aus wie List::Permutor, die von Manni vorgeschlagen wurde, erzeugt numerisch sortierten Permutationen. Das ist, was ich mit Perl gehen würde. Lassen Sie uns wissen, wie sich herausstellt.

Answer 5

Hier finden Sie aktuelle Iterator :: Array :: Jagged .

Answer 6

Versuchen Sie dies,

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

Output: Das wird die alle möglichen Kombinationen der Zahlen geben. 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