Come posso generare tutte le permutazioni di un array in Perl?

Question

Qual è il modo migliore (elegante, semplice ed efficace) per generare tutte le permutazioni n! di un array in perl?

Per esempio, se ho un allineamento @arr = (0, 1, 2), voglio uscita tutte le permutazioni:

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

probabilmente dovrebbe essere una funzione che restituisce un iteratore (pigro/valutazione in ritardo a causa n! può diventare così incredibilmente grande), in modo che possa essere chiamato in questo modo:

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

Answer 1

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

---

Utilizzare la Lista :: modulo Permutor su CPAN. Se la lista è in realtà una matrice, prova il modulo Algorithm :: Permute (anche su CPAN). E 'scritto in codice XS ed è molto efficiente:

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

Per l'esecuzione ancora più veloce, si potrebbe fare:

use Algorithm::Permute; 

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

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

Ecco un piccolo programma che genera tutte le permutazioni di tutte le parole su ogni riga di input . L'algoritmo incarnata nella funzione permute() è discusso nel Volume 4 (ancora inedito) di di Knuth The Art of Computer Programming e funziona su qualsiasi elenco:

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

L'algoritmo :: modulo Loops offre anche la NextPermute e NextPermuteNum funziona in modo efficiente per trovare tutte le permutazioni univoche di un array, anche se contiene valori duplicati, modificandolo sul posto: se i suoi elementi sono in ordine inverso, la matrice viene invertita, rendendola ordinata e restituisce false; altrimenti viene restituita la prossima permutazione.

NextPermute utilizza ordine d'archi e NextPermuteNum ordine numerico, in modo da poter enumerare tutte le permutazioni di 0..9 come questo:

use Algorithm::Loops qw(NextPermuteNum); 

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

Answer 2

potreste usare Algorithm::Permute e forse Iterating Over Permutations (The Perl Journal, autunno 1998) è una lettura interessante per voi.

Answer 3

vi suggerisco di utilizzare List::Permutor:

use List::Permutor; 

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

Answer 4

Date un'occhiata a Iterator::Array::Jagged.

Answer 5

Se si desidera scrivere il proprio, un algoritmo ricorsivo s.t. sceglierebbe un elemento dall'array e effettuerà la chiamata a se stesso con l'array più piccolo, fino alla matrice della dimensione uno.

Dovrebbe essere abbastanza pulito.

Answer 6

Mi raccomando guardando un algorithm for generating permutations in lexicographical order, che è il modo in cui ho recentemente risolto Problem 24. Quando il numero di elementi nell'array aumenta, diventa più costoso memorizzare e ordinare le permutazioni in seguito.

Sembra che List::Permutor, che è stato suggerito da Manni, genera permutazioni numericamente ordinate. Questo è quello che vorrei usare con Perl. Facci sapere come si presenta.

Answer 7

PerlMonks ha alcuni esempi: http://www.perlmonks.org/?node_id=503904

Answer 8

Prova questo,

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

uscita: Questo darà tutte le possibili combinazioni dei numeri. È possibile aggiungere la logica per filtrare le combinazioni indesiderate.

$ 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