En Perl, ¿cómo puedo obtener el producto cartesiano de múltiples conjuntos?

Question

Quiero hacer la permutación en Perl. Por ejemplo, tengo tres matrices: ["big", "tiny", "small"] y luego tengo ["red", "yellow", "green"] y también ["apple", "pear", "banana"].

¿Cómo consigo:

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

..etc.. 

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

entiendo esto se llama permutación. Pero no estoy seguro de cómo hacerlo. Además, no sé cuántas matrices puedo tener. Puede haber tres o cuatro, por lo que no quiero hacer un ciclo anidado.

Answer 1

Eso no es permutación sino Cartesian product. Ver 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"]; 

Salida:

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

Tuve que resolver este problema exacto hace unos años. Yo no era capaz de llegar con mi propia solución, sino que corrió a través de esta maravillosa pieza de código que implica un uso inteligente y juicioso de map junto con la recursividad:

#!/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í, esto parece una locura, pero me permite ¡para explicar! La función se repetirá hasta que @_ esté vacío, en cuyo punto devuelve ([1], [2], [3]) (una lista de tres arreglos de matriz) al nivel anterior de recursión. En ese nivel, $last es una referencia a una matriz que contiene [4, 5, 6].

El cuerpo del mapa exterior se ejecuta entonces tres veces con $_ conjunto a [1], entonces [2] y finalmente [3]. El mapa interno se ejecuta más de (4, 5, 6) para cada iteración del mapa exterior y esto devuelve ([1, 4], [1, 5], [1, 6]), ([2, 4], [2, 5], [2, 6]) y finalmente ([3, 4], [3, 5], [3, 6]).

La última pero una llamada recursiva devuelve ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]).

A continuación, se ejecuta ese resultado contra [7,8,9], que le da [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]

Recuerdo enviar una pregunta a perlmonks.org pedir a alguien que explicar esto a mí.

Puede adaptar fácilmente esta solución a su problema.

Answer 3

Ahora en twitter-formulario:

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

Puede usar mi módulo Set::CrossProduct si lo desea. No tiene que recorrer todo el espacio ya que le da un iterador, por lo que tiene el control.

Answer 5

SI

• no desea incluir dependencias
• usted tiene un pequeño número de matrices
• sus matrices no son realmente enorme

continuación se simplemente puede hacer esto:

Para dos matrices @xs y @ys:

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

Por tres arrays @xs, @ys, @zs

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