Comment puis-je générer toutes les permutations d'un tableau en Perl?

Question

Quel est le meilleur moyen (élégant, simple et efficace) de générer toutes les permutations n! d'un tableau en perl?

Par exemple, si j'ai un tableau @arr = (0, 1, 2) , je souhaite afficher toutes les permutations:

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

Il devrait probablement s'agir d'une fonction qui renvoie un itérateur (évaluation lazy / différée car n! peut devenir tellement grande), de sorte qu'elle peut s'appeler ainsi:

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

Answer 1

Voir perlfaq4 : " Comment permuter N éléments d’une liste? "

Utilisez le module List :: Permutor sur CPAN. Si la liste est en réalité un tableau, essayez le module Algorithm :: Permute (également sur CPAN). Il est écrit en code XS et est très efficace:

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

Pour une exécution encore plus rapide, vous pourriez faire:

use Algorithm::Permute;

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

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

Voici un petit programme qui génère toutes les permutations de tous les mots sur chaque ligne d’entrée. L'algorithme incorporé dans la fonction permute () est décrit dans le volume 4 (toujours non publié) de The Art of Computer Programming de Knuth et fonctionnera sur toutes les listes:

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

Le module Algorithm :: Loops fournit également les fonctions NextPermute et NextPermuteNum qui permettent de rechercher efficacement toutes les permutations uniques d'un tableau, même s'il contient des valeurs en double, en le modifiant sur place: si ses éléments sont triés en ordre inverse, tableau est inversé, ce qui le rend trié et renvoie false; sinon, la permutation suivante est renvoyée.

NextPermute utilise l'ordre des chaînes et l'ordre numérique NextPermuteNum, vous pouvez donc énumérer toutes les permutations de 0..9 comme ceci:

use Algorithm::Loops qw(NextPermuteNum);

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

Answer 2

Je vous suggère d'utiliser List :: Permutor :

use List::Permutor;

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

Answer 3

Vous pouvez utiliser Algorithm :: Permute et peut-être Itérer sur les permutations (The Perl Journal, automne 1998) est intéressant lire pour vous.

Answer 4

Je vous recommande de consulter un algorithme de génération de permutations dans l'ordre lexicographique , à savoir comment j'ai récemment résolu le problème 24 . Lorsque le nombre d'éléments dans le tableau devient important, il devient coûteux de stocker et de trier les permutations ultérieurement.

Il semble que List :: Permutor , suggéré par Manni, génère des permutations triées numériquement. C'est ce que je choisirais avec Perl. Dites-nous comment ça se passe.

Answer 5

Consultez Iterator :: Array :: Jagged . .

Answer 6

Essayez ceci,

use strict;
use warnings;

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

my %hash = map { 
 Essayez ceci, 

$ 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


 Sortie: Ceci donnera toutes les combinaisons possibles de nombres. Vous pouvez ajouter la logique pour filtrer les combinaisons indésirables. 

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

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

Sortie: Ceci donnera toutes les combinaisons possibles de nombres. Vous pouvez ajouter la logique pour filtrer les combinaisons indésirables.

<*>