Como posso gerar todas as permutações de uma matriz em Perl?
-
10-07-2019 - |
Pergunta
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";
}
Solução
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;
Outras dicas
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";
}
Você pode usar Algorithm :: Permuta e talvez iteração sobre permutações (The Perl Journal, Fall 1998) é um interessante leia para você.
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.
Dê uma olhada Iterator :: Matriz :: Jagged .
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