Iteration über Permutationen eines Arrays
Arbeite ich an einigen java-code für einige der Forschung, ich bin auf Arbeit, und muss einen Weg zum Durchlaufen aller Permutationen einer ArrayList. Ich habe mir über einige der vorherigen Fragen hier gestellt, aber die meisten waren nicht ganz das, was ich tun will, und diejenigen, die in der Nähe waren hatte Antworten Umgang mit strings und Beispiel-code in Perl geschrieben, oder in dem Fall der einer Implementierung, die schien, wie es funktionieren würde ... eigentlich gar nicht arbeiten.
Ideal ich bin auf der Suche nach Tipps/Codeschnipsel um mir zu helfen, schreiben Sie eine Funktion permutiert(Liste, i) als i geht von 0 bis list.size()! gibt mir jede permutation von meiner ArrayList.
- n! ziemlich groß, ziemlich schnell. Wie groß sind deine Listen?
- Da gibt es keinen Unterschied zwischen Zeichen in einem string und Knoten in eine Liste, wenn Sie reden über Permutationen.
- Haben Sie versucht, google auf
alforithm of all permutations
? Das ist eigentlich whta, die Sie brauchen - codereview.stackexchange.com/questions/11598/...
- Ich brauche nicht mehr als eine kleine Anzahl. In der Praxis werde ich mich nicht weiter zu gehen als die 24 Permutationen der 4-element-set.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Es ist eine Weise des Zählens von 0 bis (n! - 1), mit der Liste alle Permutationen einer Liste von n Elementen. Die Idee ist, zu schreiben, die zahlen, wie Sie gehen über die die Fakultät Zahlensystem und die Interpretation der Zahl als eine codierte Weise zu bestimmen, welche Kombination zu verwenden. Wenn Sie neugierig geworden sind, habe ich eine C++ - Implementierung dieses Algorithmus. Ich hab auch mal einen Vortrag über diese, in den Fall, Sie möchten einige visuals zu dem Thema.
Hoffe, das hilft!
Wenn der Iteration über alle Permutationen ist genug für Sie, Lesen Sie diese Antwort: Schrittweise durch alle Permutationen einer swap-in einer Zeit, .
Für eine gegebene
n
den iterator erzeugt alle Permutationen der zahlen0
zu(n-1)
.Sie können einfach wickeln Sie es in einem anderen iterator, der wandelt die permutation der zahlen in einer permutation der array-Elemente. (Beachten Sie, dass Sie nicht einfach ersetzen
int[]
innerhalb der iterator mit einem beliebigen array/Liste. Der Algorithmus braucht, um zu arbeiten mit zahlen.)