In Perl, come posso iterare il prodotto cartesiano di insiemi multipli?

Question

Dato numero x di array, ciascuno con un numero diverso di elementi, eventualmente, come posso scorrere tutte le combinazioni dove selezionare un elemento da ciascuna matrice?

Esempio:

[   ]   [   ]   [   ]
 foo     cat      1
 bar     dog      2
 baz              3
                  4

I ritorni

[foo]   [cat]   [ 1 ]
[foo]   [cat]   [ 2 ]
  ...
[baz]   [dog]   [ 4 ]

Lo sto facendo in Perl, btw.

Answer 1

ricorsivi e più fluente esempi Perl (con commenti e documentazione) per fare il prodotto cartesiano sono disponibili all'indirizzo http://www.perlmonks.org/?node_id=7366

Esempio:

sub cartesian {
    my @C = map { [ $_ ] } @{ shift @_ };

    foreach (@_) {
        my @A = @$_;

        @C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A;
    }

    return @C;
}

Answer 2

set :: modulo CrossProduct fa esattamente quello che vuoi. Si noti che non si è veramente alla ricerca di permutazioni, che è l'ordinamento degli elementi in un set. Siete alla ricerca di prodotto croce, che è la combinazione di elementi provenienti da diverse serie.

Il mio modulo ti dà un iteratore, in modo da non creare tutto in memoria. Si crea una nuova tupla solo quando ne avete bisogno.

use Set::Crossproduct;

my $iterator = Set::CrossProduct->new(
    [
        [qw( foo bar baz )],
        [qw( cat dog     )],
        [qw( 1 2 3 4     )],
    ]
    );

while( my $tuple = $iterator->get ) {
    say join ' ', $tuple->@*;
    }

Answer 3

Una semplice soluzione ricorsiva per un numero arbitrario di liste:

sub permute {
  my ($first_list, @remain) = @_;

  unless (defined($first_list)) {
    return []; # only possibility is the null set
  }

  my @accum;
  for my $elem (@$first_list) {
    push @accum, (map { [$elem, @$_] } permute(@remain));
  }

  return @accum;
}

Una soluzione non-così-semplice non ricorsivo per un numero arbitrario di liste:

sub make_generator {
  my @lists = reverse @_;

  my @state = map { 0 } @lists;

  return sub {
    my $i = 0;

    return undef unless defined $state[0];

    while ($i < @lists) {
      $state[$i]++;
      last if $state[$i] < scalar @{$lists[$i]};
      $state[$i] = 0;
      $i++;
    }

    if ($i >= @state) {
      ## Sabotage things so we don't produce any more values
      $state[0] = undef;
      return undef;
    }

    my @out;
    for (0..$#state) {
      push @out, $lists[$_][$state[$_]];
    }

    return [reverse @out];
  };
}

my $gen = make_generator([qw/foo bar baz/], [qw/cat dog/], [1..4]);
while ($_ = $gen->()) {
  print join(", ", @$_), "\n";
}

Answer 4

C'è un metodo ho pensato prima che utilizza una coppia per cicli e senza ricorsione.

1. trovare il numero totale di permutazioni
2. ciclo da 0 a total_permutations-1
3. osservare che, prendendo l'indice del ciclo modulo il numero di elementi di un array, è possibile ottenere ogni permutazioni

Esempio:

Dato A [3], B [2], C [3],

for (index = 0..totalpermutations) {
    print A[index % 3];
    print B[(index / 3) % 2];
    print C[(index / 6) % 3];
}

dove ovviamente un ciclo può essere sostituito per ciclare su [A B C ...], e una piccola parte può essere memoized. Naturalmente, la ricorsione è più ordinato, ma questo potrebbe essere utile per le lingue in cui la ricorsione è fortemente limitata dalla dimensione dello stack.

Answer 5

È possibile utilizzare cicli annidati.

for my $e1 (qw( foo bar baz )) {
for my $e2 (qw( cat dog )) {
for my $e3 (qw( 1 2 3 4 )) {
   my @choice = ($e1, $e2, $e3); 
   ...
}}}

Quando avete bisogno di un numero arbitrario di cicli annidati, è possibile utilizzare Algorithm :: Loops 's NestedLoops.

use Algorithm::Loops qw( NestedLoops );

my @lists = (
   [qw( foo bar baz )],
   [qw( cat dog )],
   [qw( 1 2 3 4 )],
);

my $iter = NestedLoops(\@lists);
while ( my @choice = $iter->() ) {
   ...
}