Ich habe ein Programm geschrieben, um alle möglichen Permutationen einer gegebenen Liste von Gegenständen zu finden. Das bedeutet genau, dass mein Programm alle möglichen P (n, r) -Werte für r = 0 bis n
druckt Unten ist der Code:
Ausgabe
%Vor%Mein Problem ist, als ich gehe, die Zahlen in der Eingabeliste zu erhöhen. Laufzeit erhöht sich und nach 11 Zahlen in der Eingabeliste, das Programm fast stirbt. Nimmt rund 2 GB Speicher zum Ausführen.
Ich betreibe dies auf einer Maschine mit 8 GB RAM und i5-Prozessor, so dass die Geschwindigkeit und der Platz kein Problem ist.
Ich würde mich freuen, wenn mir jemand helfen kann, einen effizienteren Code zu schreiben.
Wenn Sie alle Permutationen von 15-ish oder mehr Elementen wollen, schreiben Sie sie auf die Festplatte oder eine db oder etwas, da sie nicht in den Speicher passen. Bearbeiten: Steinhaus-Johnson-Trotter-Algorithmus . Das ist wahrscheinlich das, wonach Sie suchen.
Wenn Sie es nicht speichern - wenn Sie es gerade durchlaufen - dann überlegen Sie sich den Heaps-Algorithmus (# 3 auf Ссылка ) - oder, um Ihr Leben einfacher zu machen, verwenden Sie Guava Collections2.permutations , die nicht die gesamte Liste der Permutationen erstellt, sondern sie im Hintergrund durchläuft. (Offenlegung: Ich trage zu Guava bei.)
Java-Bibliothek von Google (Guava) hat eine Hilfsmethode dafür: Sammlungen2 # Permutationen (Sammlung)
Sie erkennen, dass Sie sehr große Listen erstellen, und dass die Laufzeit mit der Länge der Liste zunimmt. Haben Sie festgestellt, wie lange die Listen, die Ihnen Probleme bereiten, sein sollten?
Eine Sache, die einigen helfen könnte, jede Permutation so zu drucken, wie Sie sie finden, anstatt sie alle in einer Liste zusammenzufassen und dann auszudrucken. Natürlich, wenn der Punkt darin besteht, die ganze Liste tatsächlich zu speichern und sie nicht nur zu drucken, wird das nicht helfen.
Tags und Links algorithm java optimization permutation