2010-03-16 3 views
12

Ich möchte Permutation in Perl machen. Zum Beispiel habe ich drei Arrays: ["big", "tiny", "small"] und dann habe ich ["red", "yellow", "green"] und auch ["apple", "pear", "banana"].In Perl, wie kann ich das kartesische Produkt mehrerer Sätze erhalten?

Wie erhalte ich:

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

..etc.. 

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

Ich verstehe diese Permutation genannt wird. Aber ich bin nicht sicher, wie es geht. Ich weiß auch nicht, wie viele Arrays ich haben kann. Es kann drei oder vier geben, also möchte ich keine verschachtelte Schleife machen.

+0

Dies ist keine Permutation - Permutation Anordnungen eines gegebenen Satzes (z.B. {a, b, c} -> (a, b, c), (a, c, b), (b, a, c), ...). – Cascabel

+0

oh entschuldigung. Ich wusste es nicht. Sind es Kombinationen? – user295033

+0

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 –

Antwort

14

Das ist eigentlich keine Permutation aber Cartesian product. Siehe 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"]; 

Ausgang:

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
+0

Oh mein Gott. Ich hatte keine Ahnung. Das hätte mir eine Menge Kopfschmerzen erspart! –

+0

danke !!!! Das hat mir sehr geholfen. – user295033

+3

Nur eine kleine Anmerkung: Math :: Cartesian :: Product lässt Sie den gesamten Raum sofort gehen. Das könnte sein, was du willst. Wenn Sie die Kontrolle invertieren möchten, verwenden Sie Set :: CrossProduct. –

6

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.

+0

danke für Ihre Lösung, aber ich denke, Sinans Lösung ist einfacher. aber danke für das Erklären Ihrer Lösung – user295033

+0

Keine Sorge! Ich mag Sinans Lösung auch. Viel weniger kompliziert! –

5

Jetzt in twitter-Form:

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 ] 
    } [[]], @_ 
} 
+0

können Sie erklären? Das sieht cool aus! – user295033

+1

@ nubie2 Grundsätzlich ist es dasselbe wie die Lösung von Vivin Paliath, die nur eine Reduzierung statt einer Rekursion verwendet. Beginnen Sie mit einer Liste von einem 0-Tupel ('[[]]'), und hängen Sie dann für jede Arrayref in der Eingabe jedes Element an jeden der vorhandenen Einträge an. Wenn Sie wissen, was "reduce" bewirkt, ist es einfach, es auf Papier zu verfolgen. Wenn Sie nicht wissen, was "reduce" tut, lernen Sie! :) – hobbs

+0

's/solution that/solution gepostet von/' – hobbs

6

Sie können meine Set::CrossProduct Modul verwenden, wenn Sie möchten. Sie müssen nicht den gesamten Bereich durchlaufen, da Sie einen Iterator erhalten, damit Sie die Kontrolle haben.

0

IF

  • Sie nicht wollen, um Abhängigkeiten schließen
  • Sie eine kleine Anzahl von Arrays haben
  • Ihre Arrays sind nicht wirklich riesig

dann Sie kann das einfach tun:

Für zwei Arrays @xs und @ys:

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

Für drei Arrays @xs, @ys, @zs

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