Permutationen erzeugen
siehe: http://www.matheboard.de/archive/4255/3/thread.html
Ich habe die Vefahren hier mal zusammengefasst:
- Permutationen erzeugen -
I) Permutationen per Rekursion erzeugen
Probleme die saemtliche Kombinationen von Zustaenden erfordern, werden
natuerlicherweise rekursiv behandelt. Dieses Vorgehen ist sehr effizient.
Allerdings ist die Erzeugung der Daten mit dem Suchbaum stark verwoben.
Ein guter Ansatz besteht darin die Eingabe-Liste zu rotieren, um jedes
Element genau einmal zu verwenden:
### permutationen_von {1,2,3}
=== 1+ permutationen_von {23}
=== 2+ permutationen_von {31}
=== 3+ permutationen_von {12}
Sollen die Permutationen sortiert vorliegen, darf man nicht rotieren:
### permutationen_von {1,2,3}
=== 1+ permutationen_von {23}
=== 2+ permutationen_von {13}
=== 3+ permutationen_von {12}
'****** Codebeispiel in Basic: rekursiver Ansatz mit Rotation *****
perm "result= " , "abc" 'start Permutationen
SUB perm (l$, r$)
IF LEN(r$) < 1 THEN PRINT l$ 'ende der rekursion? -> Ausgabe
FOR i = 1 TO LEN(r$) 'fuer alle elemente in r$
perm l$+LEFT$(r$,1) , MID$(r$,2) 'rekursion
r$ = MID$(r$,2) + LEFT$(r$,1) 'rotiere string r$
NEXT
END SUB
'******************************************************************
II) Permutationen iterativ erzeugen
Ein alternativer Ansatz besteht darin, die Permutationen in eine lexikalische
Ordnung zu bringen. Der Vorteil dieser Loesung besteht darin, dass sie es
erlaubt allein anhand der Daten auf den Nachfolger zu schliessen.
Beschreibung:
Sortiert man eine Ziffernfolge 123-132-213-231-312-321 ergibt sich eine
natuerliche Ordnung durch den Zahlenwert der Kombinationen. (An sich ist
es egal ob man Buchstaben oder Ziffern sortiert aber mit Zahlen ist es
leichter nachzuvollziehen). Wie man sieht, ergibt sich eine Umkehrung der
Sortierung (genauer: der Algorithmus sortiert von rechts nach links
aufsteigend) also wird z.B. aus abc-acb-bac-bca-cab-cba
Vorgehensweise: --------------------------- 1432 ecfdba 123 132
1. pruefe sortierung (von re nach li) ----- -432 --fdba --3 -32
2. umbruch bei ---------------------------- 1--- -c---- -2- 1--
3. naechstgroesserer Wert aus rechter liste ---2 ---d-- --3 --2
4. tausche -------------------------------- 2431 edfcba 132 231
5. sortiere rechte liste (reverse) -------- 2134 edabcf 132 213
Codebeispiel:
Eine Implementierung in Java gibt es von sirJective auf der Seite
Permutationen 'erfassen'
Die Funktion next_permutation() ist eine Variante in C++
http://www.c-plusplus.de/forum/viewtopic...-is-178286.html
Beispiel: Permutation Rekursiv (Java Script)
<script>
document.write("<hr>Permutation mit Rotation. Aufruf permrotat '','abc' <br>");
permrotat ("","abc");
function permrotat(l,r)
{
if(r.length==1) {document.write(l+r+"<br>"); return};
for(var i=0;i<r.length;i++)
{
permrotat(""+l+r.substr(0,1), r.substr(1));
r = r.substr(1) + r.substr(0,1) /*rotiere*/
}
}
</script>
<script>
document.write("<hr>Permutation mit Sortierung. Aufruf permsort '','abc' <br>");
permsort ("","123");
function permsort(l,r)
{
if(r.length==1) {document.write(l+r+"<br>"); return};
for(var i=0;i<r.length;i++)
{
permsort(""+l+r.substr(i,1), r.substring(0,i)+r.substr(i+1));
}
}
</script>
