In Perl, come posso ottenere il prodotto cartesiano di più set?

Question

Voglio fare permutazione in Perl. Ad esempio, ho tre array: ["big", "tiny", "small"] e quindi ho ["red", "yellow", "green"] e anche ["apple", "pear", "banana"].

Come si arriva:

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

..etc.. 

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

ho capito questo si chiama permutazione. Ma non sono sicuro di come farlo. Inoltre non so quanti array posso avere. Ci possono essere tre o quattro, quindi non voglio fare il ciclo annidato.

Answer 1

In realtà non è permutazione ma Cartesian product. Vedi 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"]; 

uscita:

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

Ho dovuto risolvere questo esatto problema qualche anno fa. Non ero in grado di venire con la mia soluzione, ma invece sono imbattuto in questo meraviglioso pezzo di codice che comporta l'uso intelligente e giudizioso di map insieme con la ricorsione:

#!/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(@_); 
} 

Sì, questo sembra folle, ma mi consenta spiegare! La funzione verrà inoltrata fino a quando @_ è vuoto, a quel punto restituisce ([1], [2], [3]) (un elenco di tre arrayrefs) al livello precedente di ricorsione. A questo livello, $last è un riferimento a un array che contiene [4, 5, 6].

Il corpo della mappa esterno viene quindi eseguito tre volte con $_ insieme a [1], poi [2] e infine [3]. La mappa interna viene quindi eseguita su (4, 5, 6) per ogni iterazione della mappa esterna e restituisce ([1, 4], [1, 5], [1, 6]), ([2, 4], [2, 5], [2, 6]) e infine ([3, 4], [3, 5], [3, 6]).

La seconda chiamata ricorsiva restituisce ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]).

Poi, che gira quel risultato contro [7,8,9], che vi dà [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]

Mi ricordo di postare una domanda sul perlmonks.org chiedere a qualcuno di spiegare questo a me.

È possibile adattare facilmente questa soluzione al proprio problema.

Answer 3

Ora twitter forma:

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

È possibile utilizzare il mio modulo Set::CrossProduct, se volete. Non devi attraversare l'intero spazio poiché ti dà un iteratore, quindi hai tutto sotto controllo.

Answer 5

SE

• non si desidera includere le dipendenze
• si dispone di un piccolo numero di array
• gli array non sono davvero enorme

allora si può semplicemente fare questo:

Per due array @xs e @ys:

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

Per tre matrici @xs, @ys, @zs

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