¿Cómo puedo generar todas las permutaciones de una matriz en Perl?

Question

¿Cuál es la mejor (elegante, simple, eficiente) forma de generar todas las permutaciones n! de una matriz en perl?

Por ejemplo, si tengo una matriz @arr = (0, 1, 2), quiero salida de todas las permutaciones:

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

Probablemente debería ser una función que devuelve un iterador (perezoso evaluación/retrasado debido a n! puede llegar a ser tan imposiblemente grande), por lo que se puede llamar así:

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

Answer 1

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

---

utilizar la lista :: módulo Permutor en CPAN. Si la lista es realmente una matriz, pruebe el módulo Algorithm :: Permute (también en CPAN). Está escrito en el código XS y es muy eficiente:

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

Para la ejecución aún más rápido, se puede hacer:

use Algorithm::Permute; 

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

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

He aquí un pequeño programa que genera todas las permutaciones de todas las palabras en cada línea de entrada . El algoritmo incorporado en la función permute() se discute en el Volumen 4 (aún no publicada) de The Art of Computer Programming de Knuth y funcionará en cualquier lista:

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

El algoritmo :: módulo de bucles también proporciona el NextPermute y Funciones NextPermuteNum que encuentran eficazmente todas las permutaciones únicas de una matriz, incluso si contiene valores duplicados, modificándola in situ: si sus elementos están ordenados en orden inverso, la matriz se invierte, lo ordena y devuelve falso; de lo contrario, se devuelve la siguiente permutación.

NextPermute utiliza orden de las cuerdas y NextPermuteNum orden numérico, por lo que se puede enumerar todas las permutaciones de 0..9 así:

use Algorithm::Loops qw(NextPermuteNum); 

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

Answer 2

usted podría utilizar Algorithm::Permute y tal vez Iterating Over Permutations (El Diario Perl, otoño de 1998) es una lectura interesante para usted.

Answer 3

le sugiero que utilice List::Permutor:

use List::Permutor; 

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

Answer 4

Tome un vistazo a Iterator::Array::Jagged.

Answer 5

Si quiere escribir el suyo, un algoritmo recursivo a la vez. Elegiría un elemento fuera de la matriz y realizaría la llamada a sí mismo con la matriz más pequeña, hasta que la matriz sea del tamaño uno.

Debería estar bastante limpio.

Answer 6

Recomiendo mirar un algorithm for generating permutations in lexicographical order, que es cómo recientemente resolví Problem 24. Cuando la cantidad de elementos en la matriz aumenta, resulta costoso almacenar y ordenar las permutaciones más adelante.

Parece que List::Permutor, que fue sugerido por Manni, genera permutaciones ordenadas numéricamente. Eso es lo que usaría con Perl. Déjenos saber cómo resulta.

Answer 7

Perlmonks tiene algunos ejemplos: http://www.perlmonks.org/?node_id=503904

Answer 8

Prueba de esto,

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

salida: Esto le dará todas las combinaciones posibles de los números. Puede agregar la lógica para filtrar las combinaciones no deseadas.

$ 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