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

Question

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

Ad esempio, se ho un array @arr = (0, 1, 2) , voglio produrre 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 (valutazione pigra / ritardata perché n! può diventare così incredibilmente grande), quindi può essere chiamato così:

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

Answer 1

Vedi perlfaq4 : " Come posso permutare N elementi di un elenco? "

---

Utilizza il modulo List :: Permutor su CPAN. Se l'elenco è effettivamente un array, prova il modulo Algorithm :: Permute (anche su CPAN). È scritto nel 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 un'esecuzione ancora più veloce, puoi 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 incarnato nella funzione permute () è discusso nel volume 4 (ancora non pubblicato) di The Art of Computer Programming di Knuth e funzionerà 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;

Il modulo Algorithm :: Loops fornisce anche le funzioni NextPermute e NextPermuteNum che trovano in modo efficiente tutte le permutazioni uniche di un array, anche se contiene valori duplicati, modificandolo sul posto: se i suoi elementi sono in ordine inverso, allora il l'array viene invertito, rendendolo ordinato e restituisce false; in caso contrario viene restituita la permutazione successiva.

NextPermute utilizza l'ordine delle stringhe e l'ordine numerico NextPermuteNum, quindi puoi enumerare tutte le permutazioni di 0..9 in questo modo:

use Algorithm::Loops qw(NextPermuteNum);

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

Answer 2

Ti suggerisco di usare Elenco :: Permutor :

use List::Permutor;

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

Answer 3

Potresti usare Algorithm :: Permute e forse Iterating Over Permutations (The Perl Journal, Fall 1998) è interessante leggi per te.

Answer 4

Consiglio di guardare un per generare permutazioni in ordine lessicografico , che è come ho recentemente risolto Problema 24 . Quando il numero di elementi nell'array aumenta, diventa costoso archiviare e ordinare le permutazioni in un secondo momento.

Sembra che List :: Permutor , suggerito da Manni, generi permutazioni ordinate numericamente. Questo è quello che vorrei usare con Perl. Facci sapere come va.

Answer 5

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

Answer 6

Prova questo

use strict;
use warnings;

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

my %hash = map { 
 Prova questo 

$ 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


 Output: Questo darà tutte le possibili combinazioni dei numeri. Puoi aggiungere la logica per filtrare le combinazioni indesiderate. 

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

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

Output: Questo darà tutte le possibili combinazioni dei numeri. Puoi aggiungere la logica per filtrare le combinazioni indesiderate.

<*>