perl - sacar - permutaciones sin repeticion python

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

Question

¿Cuál es la mejor manera (elegante, simple, eficiente) de generar todo n! permutaciones 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 perezosa / retardada porque n! Puede ser 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

Consulte 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, podrías 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 discute en el Volumen 4 (aún no publicado) de El arte de la programación de computadoras 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 módulo Algorithm :: Loops también proporciona las funciones NextPermute y NextPermuteNum que encuentran de manera eficiente todas las permutaciones únicas de una matriz, incluso si contiene valores duplicados, modificándola in situ: si sus elementos están en orden inverso, la matriz se invierte , haciéndolo ordenado, y devuelve falso; de lo contrario se devuelve la siguiente permutación.

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

use Algorithm::Loops qw(NextPermuteNum);

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

Answer 2

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

Answer 3

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

Answer 4

Podría usar Algorithm::Permute y quizás Iterating Over Permutations (The Perl Journal, Fall 1998) es una lectura interesante para usted.

Answer 5

Prueba 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

Answer 6

Recomiendo mirar un algoritmo para generar permutaciones en orden lexicográfico , que es como resolví recientemente el Problema 24 . Cuando la cantidad de elementos en la matriz crece, se vuelve 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 me gustaría usar con Perl. Déjenos saber cómo resulta.

Answer 7

Si desea escribir su propio algoritmo recursivo, debe seleccionar un elemento de la matriz y realizar la llamada a sí mismo con la matriz más pequeña, hasta que la matriz sea del tamaño uno.

Debe estar bastante limpio.

Answer 8

Te sugiero que uses List::Permutor :

use List::Permutor;

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