En Perl, comment puis-je obtenir le produit cartésien de plusieurs ensembles?

Question

Je veux faire une permutation en Perl. Par exemple, j'ai trois tableaux: ["big", "tiny", "small"] et puis j'ai ["red", "yellow", "green"] et aussi ["apple", "pear", "banana"].

Comment puis-je obtenir:

["big", "red", "apple"] 
["big", "red", "pear"] 

..etc.. 

["small", "green", "banana"]

Je comprends ce qu'on appelle permutation. Mais je ne suis pas sûr de savoir comment le faire. Aussi, je ne sais pas combien de tableaux je peux avoir. Il peut y en avoir trois ou quatre, donc je ne veux pas faire de boucle imbriquée.

Answer 1

Ce n'est en fait pas une permutation mais Cartesian product. Voir Math::Cartesian::Product.

#!/usr/bin/perl 

use strict; use warnings; 

use Math::Cartesian::Product; 

cartesian { print "@_\n" } 
    ["big", "tiny", "small"], 
    ["red", "yellow", "green"], 
    ["apple", "pear", "banana"]; 

Sortie:

C:\Temp> uu 
big red apple 
big red pear 
big red banana 
big yellow apple 
big yellow pear 
big yellow banana 
big green apple 
big green pear 
big green banana 
tiny red apple 
tiny red pear 
tiny red banana 
tiny yellow apple 
tiny yellow pear 
tiny yellow banana 
tiny green apple 
tiny green pear 
tiny green banana 
small red apple 
small red pear 
small red banana 
small yellow apple 
small yellow pear 
small yellow banana 
small green apple 
small green pear 
small green banana

Answer 2

J'ai dû résoudre ce problème précis il y a quelques années. Je n'ai pas pu trouver ma propre solution, mais plutôt couru à travers ce merveilleux morceau de code qui implique l'utilisation intelligente et judicieuse de map avec récursion:

#!/usr/bin/perl 

print "permute:\n"; 
print "[", join(", ", @$_), "]\n" for permute([1,2,3], [4,5,6], [7,8,9]); 

sub permute { 

    my $last = pop @_; 

    unless(@_) { 
      return map([$_], @$last); 
    } 

    return map { 
       my $left = $_; 
       map([@$left, $_], @$last) 
       } 
       permute(@_); 
} 

Oui, cela semble fou, mais permettez-moi expliquer! La fonction se recurera jusqu'à ce que @_ soit vide, auquel cas elle renvoie ([1], [2], [3]) (une liste de trois arrayrefs) au niveau de récursion précédent. A ce niveau $last est une référence à un tableau qui contient [4, 5, 6].

Le corps de la carte externe est ensuite exécuté trois fois avec $_ ensemble à [1], puis [2] et enfin [3]. La carte interne est ensuite exécutée sur (4, 5, 6) pour chaque itération de la carte externe et renvoie ([1, 4], [1, 5], [1, 6]), ([2, 4], [2, 5], [2, 6]) et enfin ([3, 4], [3, 5], [3, 6]).

Le dernier appel récursif mais unique renvoie ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]).

Ensuite, il court contre ce résultat [7,8,9], ce qui vous donne [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]

Je me souviens de poster une question sur perlmonks.org demander à quelqu'un de me l'expliquer.

Vous pouvez facilement adapter cette solution à votre problème.

Answer 3

maintenant sur Twitter forme:

sub prod { reduce { [ map { my $i = $_; map [ @$_, $i ], @$a } @$b ] } [[]], @_ }

use strict; 
use warnings; 
use List::Util qw(reduce); 

sub cartesian_product { 
    reduce { 
    [ map { 
     my $item = $_; 
     map [ @$_, $item ], @$a 
    } @$b ] 
    } [[]], @_ 
} 

Answer 4

Vous pouvez utiliser mon module Set::CrossProduct si vous le souhaitez. Vous n'avez pas à parcourir tout l'espace car il vous donne un itérateur, donc vous avez le contrôle.

Answer 5

IF

• vous ne voulez pas inclure les dépendances
• vous avez un petit nombre de tableaux
• vos tableaux ne sont pas vraiment énorme

puis vous peut simplement faire ceci:

Pour deux tableaux @xs et @ys:

map{ my $x = $_; map { [$x, $_] } @ys } @xs 

Pour trois tableaux @xs, @ys, @zs

map{ my $x = $_; map { my $y = $_; map { [$x, $y, $_] } @zs } @ys } @xs