Wie kann ich in Perl über das kartesische Produkt von mehreren Mengen iterieren?

Question

Gegeben x Anzahl von Arrays, jedes mit einer möglicherweise unterschiedlichen Anzahl von Elementen, wie kann ich alle Kombinationen durchlaufen, bei denen ich ein Element aus jedem Array auswähle?

Beispiel:

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

Rückgabe

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

Ich mache das übrigens in Perl.

Answer 1

Meine Set::CrossProduct Modul macht genau das, was Sie wollen. Beachten Sie, dass Sie nicht wirklich nach Permutationen suchen, d. h. nach der Reihenfolge der Elemente in einer Menge. Sie suchen nach dem Kreuzprodukt, d. h. den Kombinationen von Elementen aus verschiedenen Mengen.

Mein Modul gibt Ihnen einen Iterator, so dass Sie nicht alles im Speicher erstellen müssen. Sie erstellen ein neues Tupel nur, wenn Sie es brauchen.

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 2

Eine einfache rekursive Lösung für eine beliebige Anzahl von Listen:

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

Eine nicht ganz einfache nicht-rekursive Lösung für eine beliebige Anzahl von Listen:

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 3

Rekursive und umfangreichere Perl-Beispiele (mit Kommentar und Dokumentation) für die Berechnung des kartesischen Produkts finden Sie unter http://www.perlmonks.org/?node_id=7366

Beispiel:

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

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

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

    return @C;
}

Answer 4

Sie können verschachtelte Schleifen verwenden.

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); 
   ...
}}}

Wenn Sie eine beliebige Anzahl von verschachtelten Schleifen benötigen, können Sie Algorithmus::Schleifen '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->() ) {
   ...
}

Answer 5

Es gibt eine Methode, an die ich zuerst dachte, die ein paar for-Schleifen und keine Rekursion verwendet.

1. Gesamtzahl der Permutationen ermitteln
2. Schleife von 0 bis total_permutations-1
3. Beachten Sie, dass Sie alle Permutationen erhalten können, wenn Sie den Schleifenindex als Modul der Anzahl der Elemente in einem Array nehmen

Beispiel:

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

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

wobei natürlich eine for-Schleife durch eine Schleife über [A B C ...] ersetzt werden kann, und ein kleiner Teil kann memoisiert werden. Natürlich ist eine Rekursion sauberer, aber dies könnte für Sprachen nützlich sein, in denen die Rekursion durch die Stackgröße stark eingeschränkt ist.