Permutationen 'erfassen' |
15.06.2004, 19:13 | Poff | Auf diesen Beitrag antworten » | |||||
Permutationen 'erfassen' Frage, gibts ein 'besonders' geeignetes Verfahren sämtliche Elemente einer z.B. '13 stelligen Permutation' (Permutation der Zahlengruppen bestehend aus den 13 Zahlen zw. 1 und 13, z.B. mit Pi =(7,8,9,10,11,12,6,5,4,3,13,2,1) programmiertechnisch SICHER und zudem möglichst EINFACH (Speed) zu 'erfassen' ?? ... wenn man z.B. sämtliche Elemente einer bestimmten Prüfung unterziehen will, sichergehen will dass keines übersprungen wird und zudem möglichst effizient die Elemente durchwandern will ... Das Pi von oben sollte ein Beispielelement sein (nur der Form wegen) P={(p1,p2,....,p13) | pi e {1,2,3,.....,13}, ((pi<>pj)) } (pi<>pj bei einem fixen Element versteht sich ja von selbst) |
|||||||
15.06.2004, 19:40 | SirJective | Auf diesen Beitrag antworten » | |||||
Du möchtest also alle Elemente der S_n auflisten. Ich hab da mal in PASCAL eine Funktion geschrieben, der man die aktuelle Permutation übergibt, und die die lexikalisch nächste liefert. Muss sie mal raussuchen... |
|||||||
15.06.2004, 19:55 | Mazze | Auf diesen Beitrag antworten » | |||||
ein sehr billiges verfahren wäre eine 13fache Zählschleife und die zählvariablen in das Feld schreiben, der aufwand wäre dann leider , aber du würdest nicht überprüfen müssen ob doppelte vorkommen weil das nicht der fall ist ; ). Ich kann mir vorstellen das in Knuth's 3Band was interessantes dazu steht oder im Cormen - Introductions to algorithms Das übel is das diese Bücher nich die billigsten sind aber den Cormen werd ich mir wohl auf jeden fall zulegen hm zu surjectives methodik Naja du würdest dann die 123...13 permutation als start wert geben, wenn die funktion so funktioniert wie ichs mir denke hast du 13! mal diese funktion auszuführen, denn du brauchst ja ALLE permutationen, also entsprechen alle lexikographischen erhöhungen. die frage ist jetzt was die methode selber für einen aufwand hat, sind keine schleifen drin kannste den aufwand konstant sehen sind doch welche drin müsste man den auch noch überprüfen, isses gar rekursiv darfste master theorem ansetzen ^^. aber für konstanten aufwand wäre seine methodik schneller. edit Das problem an der permutationsgeschichte ist das DU 1. alle haben willst, du kommst nicht umhin jede permutation min. einmal anzufassen, da jede verschieden ist, ergo musst du mindesten n! mal in das feld oder wo auch immer du sie haben willst speichern 2. du nach nicht zählenden algorithmen überprüfen musst ob doppelte vorhanden sind (bei jectives und meiner methode nicht möglich) Ich habe mir überlegt ob man das problem per divide and conquer reduzieren kann dürfte aber nicht möglich sein Wenn du von 0 anfängst wirst du wohl oder übel alle n! permutationen berechnen müssen, wie sonst willst du sie haben wenn nicht so? |
|||||||
15.06.2004, 20:16 | Leopold | Auf diesen Beitrag antworten » | |||||
Schaut einmal nach bei http://www.matheboard.de/thread.php?thre...448&page=2&sid= Da habe ich so etwas für Visual Basic |
|||||||
15.06.2004, 20:21 | SirJective | Auf diesen Beitrag antworten » | |||||
War doch nicht Pascal, sondern Java. Ich hoffe, ihr versteht's. Ob das jetzt besonders effizient ist, müsst ihr entscheiden. Für meine Zwecke war es stets ausreichend.
|
|||||||
15.06.2004, 20:22 | Mazze | Auf diesen Beitrag antworten » | |||||
naja Leopold, hie rgehts wohl um Aufwand, also möglichst effektiv zu programmieren, und so wie sich der thread ließt scheint dein Code sämtliche möglichkeiten durchzurechnen ergo für die eingabe länge n berehcnet dein algorithmus n! möglichkeiten A(n) = n! das is nur grob abgeschätzt da ich dein algorithmus nich kenne aber wenn du alle möglichkeiten expliziet berechnest das ist n! die untere Schranke der Aufwandsfunktion! hm du ahst also 2 Schleifen drin Beim aufwand geht man immer vom worst case aus! entpsrechend würde deine while schleife im worst case n mal über das Feld gehen => aufwand n die zweite schleife is lediglich für das sortieren hat also mit der berechnung erstmal nichts zu tun Um an alle elemente ranzukommen würde nach deiner Methode ein aufwand von A(n) = n*n! im worst case auftreten, jetzt könnt ihr ja abschätzen ob oder n*n! stärker wächst! |
|||||||
Anzeige | |||||||
|
|||||||
15.06.2004, 20:47 | Poff | Auf diesen Beitrag antworten » | |||||
.... erstmal Ddankee. Das 'Problem' ist nicht, dass ich keine Lösung oder keine Idee gehabt hätte wie da evtl ranzugehen, sondern es geht mehr um Effizienz, um möglichst gutes Vermeiden überflüssiger Sequenzen Abfragen und Sonstigem. Speicherplatz ist kein Thema, die Elemente werden 'On the Fly' verarbeitet und sind dann ERLEDIGT. Völlig klar ist, dass jedes Element mindestens 1 mal angefasst werden muss, und damit ist erstmal ein nicht unterschreitbares 'Minimum' definiert. Zum anderen gibt es aber verschiedene Möglichkeiten wie man jeweils zum 'nächsten' Element kommen kann und dieser Weg muss ja GENAUSO oft durchlaufen werden wie es verschiedene Elemente gibt (mal unterstellt der Weg sei 'konstant') Es ist also klar, dass dies ELEMENTAR für die Gesamtrechenzeit ist und es hätte ja sein können, dass es evtl einen besonders prädestinierten Weg gibt, wie z.B. bei Sortierungen oder sonstigen Dingen mitunter .... |
|||||||
15.06.2004, 20:55 | Mazze | Auf diesen Beitrag antworten » | |||||
Die richtig cleveren algorithmen sind sehr abstrakt, und meistens hamse augenscheinlich nicht mehr viel mit dem problem zu tun, hab ich schon oft gesehn : ). mir ist leider noch kein genialer algorithmus für permutationen unter die augen gekommen http://schulinformatik.at/fachdidaktik/p...n-rekursion.htm Schau dir das mal an, offensichtlich eignet sich ne baumstruktur ums zu vereinfachen, bin nur kurz drüber geflogen |
|||||||
16.06.2004, 00:25 | SirJective | Auf diesen Beitrag antworten » | |||||
Wenn du mit einem rekursiven Algorithmus klar kommst, Poff, dann funktioniert auch folgendes, und das ist mit das schnellste, was ich mir vorstellen kann: (EDIT - Komplettes Programm mit Zählern eingefügt. Siehe einige Beiträge weiter unten.)
Wird die Idee klar? Der Trick ist, nicht die verbleibenden Zahlen als Liste zu übergeben, oder jede Zahl darauf zu testen, ob sie von allen vorigen verschieden ist, sondern in einem Bitfeld zu sagen, welche Zahlen noch "frei" sind. Wenn es auf die Reihenfolge derr Permutationen nicht ankommt, findet man vielleicht einen Weg, sie so anzuordnen, dass von einer zur nächsten nur je eine Transposition nötig wird. Hab aber keine Ahnung, welche Reihenfolge das für ein allgemeines n wäre. Aber darüber gibt's bestimmt auch schon Untersuchungen. Gruss, SirJective |
|||||||
16.06.2004, 01:03 | Poff | Auf diesen Beitrag antworten » | |||||
Ja, hab ich verstanden und auch sofort gesehen worauf du rauswillst, da hatte ich noch nicht gesehen dass auch noch ein erklärender Text unten nachfolgt .... *g* automatische Verknappung der Angebotsmenge, anstatt auf andere Art abzufragen und Co. 'Sowas' schwebte mir auch vor. Nur, wenn ich das richtig sehe produziert das 'permutiere' beim Aufruf ein Element für das gegeben ist, dass alle Stellen verschieden sind und das dann an Ort und Stelle auch gleich verarbeitet werden kann aber sonst scheint mir das noch nichts weiter intelligentes am Hals zu haben .... (scheinen noch ein paar 'Lücken' drin, aber darum gehts mal nicht) ... Sag mal, zyklische Gruppen sind das keine, diese Permutationen ?? ... nein, ich sehe gerade das scheint schon das ganze Möglichkeiten- feld durchzulaufen entsprechend einer 'anzahl'-fachen verschachtelten Schleife, kann ich aber nicht ganz klar sehen, hab da etwas Probs mit den Begin-End Zuordnungen und auch etwas mit der Pascal-Syntax. .... so machts aber schon mehr Sinn . |
|||||||
16.06.2004, 11:07 | Irrlicht | Auf diesen Beitrag antworten » | |||||
Die symmetrischen Gruppen sind mit Ausnahme der S_1 und der S_2 nicht zyklisch. Die anderen S_n werden von 2 Elementen erzeugt, aber ich glaube nicht, dass es hier hilfreich ist. |
|||||||
16.06.2004, 16:11 | Mazze | Auf diesen Beitrag antworten » | |||||
kannst du mal "anzahl" in deinem code näher spezifizieren? Sollte anzahl die anzahl der möglichkeiten liefern ist der Algorithmus superexponentiel im wachstum und nicht zu gebrauchen! |
|||||||
16.06.2004, 16:42 | SirJective | Auf diesen Beitrag antworten » | |||||
Mazze: Soweit ich Poffs Problem verstanden habe, sucht er nach einem schnellen Algorithmus, um sich alle Permutationen der Zahlen von 1 bis n liefern zu lassen. Da das genau n! Stueck sind, hat jeder Algorithmus eine Laufzeit, die mindestens in der Groessenordnung O(n!) liegt - es sei denn, du findest eine Moeglichkeit, laengere Permutationen schneller als kuerzere Permutationen zu liefern (als Zeit pro Permutation). Mein iterativer Algorithmus hat eine Laufzeit von O(n! * n * log(n)), wenn man die Insertionsort durch eine O(n * log(n))-Sortierung ersetzt. Mein rekursiver Algorithmus hat eine Laufzeit von O(n! * n). Der Parameter "anzahl" in meinem Code ist gerade dieses n, die Anzahl der zu permutierenden Zahlen. Gruss, SirJective |
|||||||
16.06.2004, 17:10 | Mazze | Auf diesen Beitrag antworten » | |||||
hm also n gleich die anzahl der permutierenden Zeichen also O(n!*n) ist er sicher nicht. Folgendes, sofern der Rekursionsanker nicht erfüllt ist wird eine zählschleife aufgerufen.Die Zählschleife zählt immer bis n, dabei ist egal was sie macht, die Takte werden trotzdem verbraucht. Eine zählschleife die nichts macht sondern nur zählt hat bereits den aufwand n. Sollte die Bedingung in der Schleife nicht erfüllt sein springt er in die rekursion. Wie man sieht wird genau (n-1) mal die rekursion aufgerufen. In jeder rekursionstufe der (n-1) rekursionen wird die zählschleife VOLL durchgezählt, das kostet zeit auch wenn nichts passiert. die zählschleifen sind verschachtelt, da du den besetzt wert immer wieder auf false setzt nach der rekursion, muss also auch die (n-1)te Schleife einen rekursionsaufruf beinhalten. Effektiv geht dein algorithmus n-1 geschachtelte schleifen n mal durch das müsste sein |
|||||||
16.06.2004, 22:22 | SirJective | Auf diesen Beitrag antworten » | |||||
Ich hab jetzt die Methode zu einem kompletten Programm ergänzt. Die Methode tut genau was ich vorhergesagt habe, mit genau der Laufzeit, die ich vorhergesagt habe. Ich zähle hier die Anzahl der Funktionsaufrufe und die Anzahl der Schleifendurchläufe. (Zähler pe liefert die Anzahl der Permutationen, die ist wie erwartet gleich .) Für die Anzahl n von 1 bis 10 hab ich's durchlaufen lassen, und das Ergebnis, was mich selbst ein bisschen überrascht hat, ist: Die Anzahl der Funktionsaufrufe (Zähler f) ist gleich . Die Anzahl der Schleifendurchläufe (Zähler p) ist gleich . Dabei ist [.] die Gaußklammer (Abrundung). Damit ist - wenigstens in diesem Bereich - die Laufzeit von der Ordnung O(n!*n). Mazze, du übersiehst, dass die zweite Schleife ihrerseits die Funktion nur n-2 mal aufruft, und die dritte Schleife nur n-3 mal etc. |
|||||||
16.06.2004, 22:48 | Poff | Auf diesen Beitrag antworten » | |||||
@SirJective, wenn das so ist wie du schreibst, --was ist stark annehmen will--, dann erscheint mir das 'optimal' ... was ist denn bitte dieses 'e' bei der 'Laufzeitabschätzung' ? |
|||||||
16.06.2004, 23:43 | Irrlicht | Auf diesen Beitrag antworten » | |||||
16.06.2004, 23:44 | Mazze | Auf diesen Beitrag antworten » | |||||
hm , jetzt muss ich mich aber lansgam doch sehr wundern... ungeachtet von dem was passiert mal durchgehen Zustand 1: stufe=1; anzahl= 5; stufe != 5 Zählschleife #1 startet durchlauf mit 1 da bedingung bereits beim ersten mal erfüllt => Sprung in rekursion stufe=2; anzahl = 5 stufe != 5 zählschleife startet durchlauf mit 1 bedingung nicht erfüllt zählschleife +1 //zählt effektiv n mal durch bedingung erfüllt sprung in rekursion // ruft aber nur n-1 mal auf hm effektiv wird 1 ja nicht mehr geprüft für die Oberschleife, das heißt tatsächlich das genau ein Durchlauf nicht mehr getan werden muss. Das zieht sich dann runter bis ans ende. =>n*(n-1)*(n-2)...(n-(n-1)) hoffe das is jetzt richtig -.- Die vorletze muss folgerichtig nur noch einmal aufrufen Ich frag mich nur noch wieso n*(n-1) ... *(n-(n-1)) lineare resultate liefert ... edit ehm was ich hier beschrieben hab is n! das sind die aufrufe :P so jetzt bin ich aufeinmal schneller als du was hab ich nu vergessen? -.- |
|||||||
16.06.2004, 23:48 | Poff | Auf diesen Beitrag antworten » | |||||
Irrlicht Thanks .... ich weiß zwar nicht wie das da rein kommt, ist mir ehrlich gesagt aber auch egal ... |
|||||||
17.06.2004, 09:48 | SirJective | Auf diesen Beitrag antworten » | |||||
Ähm... ich muss das Programm doch nochmal anschauen... irgendwas scheint da immer noch nicht zu stimmen! Mazze, was meinst du mit "lineare resultate"? Momentan sieht es so aus: Die Anzahl der Funktionsaufrufe erster Stufe ist gleich 1. Die Anzahl der Funktionsaufrufe zweiter Stufe ist gleich n. Die Anzahl der Funktionsaufrufe dritter Stufe ist gleich n*(n-1). ... Die Anzahl der Funktionsaufrufe k-ter Stufe ist gleich n*(n-1)*...*(n-(k-2)). ... Die Anzahl der Funktionsaufrufe (n-1)-ter Stufe ist gleich n*(n-1)*...*3. Die Anzahl der Funktionsaufrufe n-ter Stufe ist gleich n*(n-1)*...*2. Die Anzahl aller Funktionsaufrufe ist die Summe all dieser. Diese Zahl kann man auch als schreiben. Die zu (e-1) fehlenden Summanden sind anscheinend in Summe kleiner als 1/n!. |
|||||||
02.08.2007, 13:10 | Tim69 | Auf diesen Beitrag antworten » | |||||
würde gerne mal hierauf noch verweisen: http://marknelson.us/2002/03/01/next-permutation/ demnach ist die rekursive variante nicht die schnellste, die andere habe ich allerdings noch nicht verstanden. hat wohl was mit zeigern zu tun ... |
|||||||
22.07.2010, 01:44 | nikorama | Auf diesen Beitrag antworten » | |||||
permutationen erzeugen 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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |