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

Question

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

Por ejemplo, si tengo una matriz @arr = (0, 1, 2) , quiero generar 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 (evaluación diferida / diferida porque n! puede llegar a ser tan increíblemente grande), por lo que puede llamarse así:

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

Answer 1

Ver perlfaq4 : " ¿Cómo permuto N elementos de una lista? "

---

Utilice el módulo List :: Permutor en CPAN. Si la lista es realmente una matriz, pruebe el módulo Algorithm :: Permute (también en CPAN). Está escrito en 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 una ejecución aún más rápida, puede hacer:

use Algorithm::Permute;

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

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

Aquí hay 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 analiza en el Volumen 4 (aún no publicado) de Knuth's The Art of Computer Programming 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 módulo Algorithm :: Loops también proporciona las funciones NextPermute y NextPermuteNum que encuentran eficientemente todas las permutaciones únicas de una matriz, incluso si contiene valores duplicados, modificándola en el lugar: si sus elementos están en orden inverso, entonces el La matriz se invierte, ordenándola, y devuelve falso; de lo contrario, se devuelve la próxima permutación.

NextPermute utiliza el orden de las cadenas y el orden numérico NextPermuteNum, por lo que puede enumerar todas las permutaciones de 0..9 de esta manera:

use Algorithm::Loops qw(NextPermuteNum);

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

Answer 2

Le sugiero que use Lista :: Permutor :

use List::Permutor;

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

Answer 3

Puede usar Algorithm :: Permute y tal vez Iterando las permutaciones (The Perl Journal, Fall 1998) es un interesante leer para ti

Answer 4

Recomiendo mirar un algoritmo para generar permutaciones en orden lexicográfico , que es cómo resolví recientemente el Problema 24 . Cuando el número de elementos en la matriz aumenta, se vuelve costoso almacenar y ordenar las permutaciones más adelante.

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

Answer 5

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

Answer 6

Prueba esto,

use strict;
use warnings;

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

my %hash = map { 
 Prueba esto, 

$ 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


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

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

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

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

<*>