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(""+reverse("")+"<br>");
function reverse(s)
{
if(s.length==1) return s;
return (reverse(s.substr(1))+s.substr(0,1));
}
</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>
<hr>