Como posso gerar todas as permutações de uma matriz em Perl?

Question

Qual é a melhor (elegante, simples, eficiente) maneira de gerar todas as permutações n! de uma matriz em Perl?

Por exemplo, se eu tiver uma @arr = (0, 1, 2) array, eu quero saída todas as permutações:

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

Ele provavelmente deve ser uma função que retorna um iterador (avaliação preguiçosa / adiada porque n! pode se tornar tão incrivelmente grande), então ele pode ser chamado assim:

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

Answer 1

perlfaq4 : "Como faço para permutar N elementos de uma lista?"

---

Use o módulo Lista :: Permutor no CPAN. Se a lista é realmente um array, tente o módulo Algorithm :: Permuta (também no CPAN). Ele é escrito em código XS e é muito 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 a execução ainda mais rápido, você pode fazer:

use Algorithm::Permute;

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

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

Aqui está um pequeno programa que gera todas as permutações de todas as palavras em cada linha de entrada. O algoritmo incorporado no permute () função é discutida no Volume 4 (ainda não publicado) de Knuth The Art of Computer Programming e vai trabalhar em qualquer 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;

O módulo de algoritmo :: Loops também fornece as funções NextPermute e NextPermuteNum que encontram de forma eficiente todas as permutações únicas de uma matriz, mesmo que contém valores duplicados, modificando-o no local: se os elementos estão em ordem inversa-ordenada, em seguida, o matriz é invertida, tornando-classificado, e ele retorna false; caso contrário, a próxima permutação é retornado.

NextPermute usa a ordem de cordas e ordem numérica NextPermuteNum, para que possa enumerar todas as permutações de 0..9 assim:

use Algorithm::Loops qw(NextPermuteNum);

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

Answer 2

Eu sugiro que você use href="http://search.cpan.org/perldoc?List::Permutor" :: Permutor :

use List::Permutor;

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

Answer 3

Você pode usar Algorithm :: Permuta e talvez iteração sobre permutações (The Perl Journal, Fall 1998) é um interessante leia para você.

Answer 4

Eu recomendo a olhar para um algoritmo para gerar permutações em ordem lexicográfica, que é como eu recentemente resolvido Problema 24 . Quando o número de itens na matriz cresce grande, torna-se caro para armazenar e classificar permutações mais tarde.

Parece que List::Permutor, que foi sugerido por Manni, gera numericamente permutações ordenadas. Isso é o que eu iria com usando Perl. Deixe-nos saber como ele sair.

Answer 5

Dê uma olhada Iterator :: Matriz :: Jagged .

Answer 6

Tente este,

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

Saída: Isto vai dar os todas as combinações possíveis dos números. Você pode adicionar a lógica para filtrar as combinações indesejadas.

$ 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