Dies ist nicht das Standardpartitionierungsproblem, da ich die Reihenfolge der Elemente in der Liste beibehalten muss.
Also zum Beispiel wenn ich eine Liste habe
%Vor%und ich möchte zwei Chunks, dann sollte der Split
geben %Vor%für eine Summe von 17 auf jeder Seite. Für drei Chunks wäre das Ergebnis
%Vor%für Summen von 12, 12 und 10.
Für zusätzliche Erklärungen bearbeiten
Ich teile die Summe momentan mit der Anzahl der Chunks und benutze diese als Ziel, dann iteriere bis ich nahe an das Ziel komme. Das Problem ist, dass bestimmte Datensätze den Algorithmus durcheinander bringen können, indem Sie beispielsweise versuchen, das Folgende in 3 zu unterteilen: -
%Vor%Summe ist 300, Ziel ist 100. Der erste Brocken würde zu 95 summieren, der zweite wäre Summe zu 90, der dritte würde zu 110 summieren, und 5 wäre "übrig". Wenn man es dort anhängt, wo es sein soll, ergibt das 95, 90, 115, wo eine "vernünftigere" Lösung 110, 100, 90 wäre.
Ende bearbeiten
Hintergrund:
Ich habe eine Liste mit Text (Songtexten) unterschiedlicher Höhe, und ich möchte den Text in eine beliebige Anzahl von Spalten aufteilen. Derzeit berechne ich eine Zielhöhe basierend auf der Gesamthöhe aller Linien, aber das ist offensichtlich eine konsistente Unterschätzung, die in einigen Fällen zu einer suboptimalen Lösung führt (die letzte Spalte ist deutlich größer).
Dieser Ansatz definiert Partitionsgrenzen, die das Array in ungefähr gleiche Anzahl von Elementen aufteilen, und sucht dann wiederholt nach besseren Partitionierungen, bis es nicht mehr gefunden werden kann. Es unterscheidet sich von den meisten anderen veröffentlichten Lösungen darin, dass es versucht, eine optimale Lösung zu finden, indem es mehrere verschiedene Partitionierungen versucht. Die anderen Lösungen versuchen, eine gute Partition in einem einzigen Durchlauf durch das Array zu erstellen, aber ich kann mir keinen Algorithmus mit einem Durchlauf vorstellen, der garantiert optimal ist.
Der Code hier ist eine effiziente Implementierung dieses Algorithmus, aber es kann schwer zu verstehen sein, so dass eine besser lesbare Version als Anhang am Ende enthalten ist.
%Vor%Je nachdem, was Sie damit machen, können einige Änderungen vorgenommen werden. Um beispielsweise festzustellen, ob die beste Partitionierung gefunden wurde, stoppt dieser Algorithmus, wenn zwischen den Partitionen kein Höhenunterschied besteht. Er findet nichts Besseres als das Beste, was er für mehr als 5 Iterationen in einer Zeile oder nach 100 gesehen hat Gesamtwiederholungen als Auffangpunkt. Möglicherweise müssen Sie diese Konstanten anpassen oder ein anderes Schema verwenden. Wenn Ihre Höhen eine komplexe Landschaft von Werten bilden, kann das Wissen darüber, wann man aufhören muss, in klassische Probleme geraten, indem versucht wird, lokalen Maxima und solchen Dingen zu entgehen.
Der neue Testfall wurde hinzugefügt, [95, 15, 75, 25, 85, 5], den diese Methode korrekt behandelt.
Diese Version des Algorithmus ist leichter zu lesen und zu verstehen, ist aber ein wenig länger, weil weniger Vorteile von integrierten Python-Funktionen genutzt werden. Es scheint jedoch in einer vergleichbaren oder sogar etwas schnelleren Zeit ausgeführt zu werden.
%Vor%Hier ist der beste O (n) Greedy-Algorithmus, den ich für jetzt habe. Die Idee besteht darin, Elemente aus der Liste gierig an einen Chunk anzuhängen, bis die Summe für den aktuellen Chunk die durchschnittliche erwartete Summe für einen Chunk an diesem Punkt übersteigt. Die durchschnittlich erwartete Summe wird ständig aktualisiert. Diese Lösung ist nicht perfekt, aber wie gesagt, es ist O (n) und hat mit meinen Tests nicht schlecht funktioniert. Ich bin gespannt auf Feedback und Verbesserungsvorschläge.
Ich habe meine Debug-Print-Anweisungen im Code gelassen, um einige Dokumentationen bereitzustellen. Fühlen Sie sich frei, sie zu kommentieren, um zu sehen, was in jedem Schritt vor sich geht.
CODE
%Vor%TESTCODE
%Vor%TESTS mit Ihrer Liste:
%Vor%TESTS mit zufälligen Listen der Länge 100 und Elementen von 1 bis 100 (Drucken der Zufallsliste entfällt):
%Vor%Wie Sie sehen können, wird es immer schlimmer, je mehr Chunks Sie erzeugen wollen. Ich hoffe ich konnte etwas helfen.
edit: Die yield from -Syntax benötigt Python 3.3 oder neuer, wenn Sie eine ältere Version verwenden, wird die Anweisung in eine normale for-Schleife umgewandelt.
Das kommt etwas spät, aber ich habe eine Funktion entwickelt, die das tut, was Sie brauchen. Es braucht einen zweiten Parameter, der sagt, wie es die Liste aufteilen soll
%Vor%es würde für 4 Divisionen fehlschlagen, weil Sie offensichtlich in Ihrer Frage angegeben haben, dass Sie die Reihenfolge beibehalten möchten
%Vor%und Ihre Sequenz kann nicht mit dieser übereinstimmen
Hier ist ein Code, der für jede Unterliste 2-ples von Schichtindizes zurückgibt.
%Vor%Ausgabe ist:
%Vor%So könnte ich dieses Problem für den Fall von zwei gewünschten Unterlisten angreifen. Es ist wahrscheinlich nicht so effizient wie es sein könnte, aber es ist ein erster Schnitt.
%Vor%Sie können es hier in Aktion sehen:
%Vor%Ich werde Ihnen andere Fälle als Übung überlassen. :)
Tags und Links python algorithm partitioning order