Community  »  Perl: Allgemeines Forum

Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
Hallo zusammen, habe ein Algorithmisproblem mit dem ich nicht so ganz zurecht komme. Folgende Problemstellung. Ich hab z.B. X Arrays mit jeweils n (n verschieden für jedes x)Einträgen Bsp: Array a = "a1", "a2", "a3" Array b = "b1", "b2", "b3", "b4" Array c = "c1", "c2" ... ... Array x = "x1", ... xn Was nun gefordert wird ist eine Methode um alle möglichen Permutationen auszugeben, also a1, b1, c1 a1, b1, c2 a1, b2, c1 ... ... a3, b4, c2 Problem dabai ist, dass sowohl die Anzahl der Array als auch die Anzahl der Elemente in jedem Array nicht festgelegt ist. Hat da jemand eine Lösung? Danke und Grüsse spline Datum: 16.06.2006-09:12
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
Hi, ich weiss zwar nicht wo dein problem liegt, aber is doch ganz einfach: for my $a (0..$#arr1) { for my $b (0..$#arr2) { for my $c (0..$#arr3) { print "$a, $b, $c"; } } } oder versteh ich da was falsch? Datum: 16.06.2006-10:31
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
Servus, die Lösung ist leider zu einfach. Du verschachtelst hier drei Schleifen inneinander. Das funktioniert, wenn ich genau drei Arrays habe. aber ich hatte ja geschrieben, dass die Anzahl der Arrays nicht bekannt ist. Hier klappts dann schon wieder nicht mehr, da man hier 4 Schleifen verschachteln müsste @arr = ( ["a1", "a2", "a3", "a4"], ["b1", "b2", "b3"], ["c1", "c2"], ["d1", "d2"] ); Grüsse spline Datum: 16.06.2006-10:47
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
hallo spline, ich hoffe das ist nicht für eine web anwendung gedacht denn damit kannst du ganz schnell den server abschiessen. Hier mal ein kleines Rechenbeispiel mit deinem beispiel Array: 4*3*2*2 = 48 Schleifen durchläufe. Sprich wenn das ganze nen bisschen komplexer wird sagen wir mal: 5 * 4 * 3 * 2 * 6 = 720 Schleifen durchläufe das kann wahnsinnig auf die CPU schlagen und dein provider macht dir das Script dicht. Hab schon ein paar mal nen server mit sowas aus dem netzt gekickt *G* :) Datum: 16.06.2006-14:45
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
sub permute { my ($aoa) = @_; return if !($aoa && @$aoa); my ($first, @rest) = @$aoa; my @perms; for my $f (@$first) { if (my @rp = permute(\@rest)) { push @perms, map { [$f, @$_] } @rp; } else { push @perms, [$f]; } } return @perms; } my @p = permute(\@aoa); use Data::Dumper; print Dumper \@p; Datum: 16.06.2006-15:21
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
Hallo tinita, leider versteh ich Deine Funktion nicht, weil meine Perl-Kenntnisse da dann doch am Ende sind. Wenn ich sie folgendermassen aufrufe @arr = ( ["a1", "a2", "a3", "a4"], ["b1", "b2", "b3"], ["c1", "c2"], ["d1", "d2"] ); permute @arr kommt ausser einem $VAR1 = [] nichts. Kannst Du mir bitte mal ein Beispiel für einen Aufruf geben? Danke spline Datum: 15.07.2006-22:52
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
Arghhhh, mein Fehler. War zu doof um die Funktion aufzurufen. Hatte etwas übsersehen. Jetzt muss ich nur nich die Ausgabe zeilenwiese in eine Datei schreiben. Danke spline Datum: 15.07.2006-23:00
re: Algorithmis für Permutationen - 2-dimensionales Array	Seitenanfang
Hallo, konnte den Algorithmus urlaubsbedint erst vor ein paar Tagen testen. Funktioniert gut und ist auch fix. Allerdings ergibt sich aus der Rekursion ein sehr hoher Speicherbedarf, der bei einem groesserem Array (3-8 x 5-7) dazu führt, dass Windows nach 30 Minuten ein Problem mit der Auslagerungsdatei bekommt und das Programm abschmiert. Hat jemand auch eine nicht rekursive Lösung parat? Danke schon mal spline Datum: 19.07.2006-08:19