Ich musste dieses genaue Problem vor ein paar Jahren lösen. Ich war nicht in der Lage, mit meiner eigenen Lösung zu kommen, sondern lief über dieses wunderbare Stück Code, der zusammen mit Rekursion kluge und umsichtige Verwendung von map
beinhaltet:
#!/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(@_);
}
Ja, das verrückt aussieht, aber mich erlauben erklären! Die Funktion wird rekursiv ausgeführt, bis @_
leer ist. An diesem Punkt wird ([1], [2], [3])
(eine Liste von drei Arrayrefs) an die vorherige Rekursionsebene zurückgegeben. Auf dieser Ebene ist $last
eine Referenz auf ein Array, das [4, 5, 6]
enthält.
Der Körper der äußeren Karte wird dann dreimal mit $_
Satz [1]
laufen, dann [2]
und schließlich [3]
. Die innere Karte wird dann über (4, 5, 6)
für jede Iteration der äußeren Karte durchlaufen, und dies gibt ([1, 4], [1, 5], [1, 6])
, ([2, 4], [2, 5], [2, 6])
und schließlich ([3, 4], [3, 5], [3, 6])
zurück.
Der vorletzte rekursive Aufruf gibt ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6])
zurück.
Dann, läuft es dieses Ergebnis gegen [7,8,9]
, die Sie [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]
gibt Ich erinnere mich, eine Frage auf perlmonks.org Posting jemand fragen mir dies zu erklären.
Sie können diese Lösung problemlos an Ihr Problem anpassen.
Dies ist keine Permutation - Permutation Anordnungen eines gegebenen Satzes (z.B. {a, b, c} -> (a, b, c), (a, c, b), (b, a, c), ...). – Cascabel
oh entschuldigung. Ich wusste es nicht. Sind es Kombinationen? – user295033
Tatsächlich habe ich gerade festgestellt, dass dies ein Duplikat ist: Siehe http://stackoverflow.com/questions/1256036/in-perl-how-can-i-iterate-over-the-cartesian-product-of-multiple-sets –