Ich suche nach einem Algorithmus zum Verteilen von Werten aus einer Liste, damit die resultierende Liste möglichst "ausgeglichen" oder "gleichmäßig verteilt" ist (in Anführungszeichen, da ich nicht sicher bin, ob dies die beste Art ist, sie zu beschreiben ... Später werde ich einen Weg zeigen, um zu messen, ob ein Ergebnis besser ist als das andere.
Also, für die Liste:
[1, 1, 2, 2, 3, 3]
Eines der besten Ergebnisse nach der Neuverteilung der Werte ist:
[1, 2, 3, 1, 2, 3]
Möglicherweise gibt es andere so gute Ergebnisse wie dieses, und dies wird natürlich mit einem weniger einheitlichen Satz von Werten komplizierter.
So messen Sie, ob ein Ergebnis besser ist als andere:
Zählen Sie die Abstände zwischen jedem Artikel und dem nächsten Artikel mit demselben Wert.
Berechnen Sie die Standardabweichung für diesen Abstandssatz. Eine geringere Dispersion bedeutet ein besseres Ergebnis.
Beobachtungen:
- Wenn eine Entfernung berechnet wird und das Ende der Liste erreicht ist, ohne einen Artikel mit demselben Wert zu finden, kehren wir zum Anfang der Liste zurück. Es wird also höchstens derselbe Artikel gefunden, und der Abstand für diesen Artikel entspricht der Länge der Liste. Dies bedeutet, dass die Liste zyklisch ist .
- Eine typische Liste enthält ~ 50 Elemente mit ~ 15 verschiedenen Werten in unterschiedlichen Mengen.
So:
- Für das Ergebnis
[1, 2, 3, 1, 2, 3]
sind die Abstände[3, 3, 3, 3, 3, 3]
und die Standardabweichung ist0
; - Für das Ergebnis
[1, 1, 2, 2, 3, 3]
sind die Abstände[1, 5, 1, 5, 1, 5]
und die Standardabweichung ist2
; - Damit ist das erste Ergebnis besser als das zweite (geringere Abweichung ist besser).
Angesichts dieser Definitionen frage ich nach einem Hinweis, nach welchen Algorithmen oder Strategien ich suchen soll.
quelle
Antworten:
Ich bin auf diese Frage gestoßen, als ich ein ähnliches Problem untersucht habe: optimale Flüssigkeitszugaben zur Reduzierung der Schichtung. Meine Lösung scheint auch auf Ihre Situation anwendbar zu sein.
Wenn Sie die Flüssigkeiten A, B und C im Verhältnis 30,20,10 (dh 30 Einheiten A, 20 Einheiten B und 10 Einheiten C) mischen möchten, erhalten Sie eine Schichtung, wenn Sie alle addieren das A, dann das ganze B und dann das ganze C. Es ist besser, kleinere Einheiten zu mischen. Fügen Sie beispielsweise einzelne Einheiten in der Reihenfolge [A, B, A, C, B, A] hinzu. Das wird eine Schichtung insgesamt verhindern.
Ich habe es als eine Art Zusammenführung behandelt, die eine Prioritätswarteschlange verwendet. Wenn ich eine Struktur zur Beschreibung der Ergänzungen erstelle:
Die Frequenz wird als "Eins alle N" ausgedrückt. Also hat A, das von sechs zu drei addiert wird, eine Frequenz von 2 (6/3).
Und initialisiere einen Heap, der anfänglich enthält:
Jetzt entferne ich das erste Objekt aus dem Heap und gebe es aus. Reduzieren Sie dann die Anzahl um 1, erhöhen Sie die Priorität nach Häufigkeit und fügen Sie sie wieder dem Heap hinzu. Der resultierende Heap ist:
Entfernen Sie anschließend B aus dem Heap, geben Sie es aus und aktualisieren Sie es. Fügen Sie es dann wieder zum Heap hinzu:
Wenn ich so weitermache, erhalte ich die gewünschte Mischung. Ich verwende einen benutzerdefinierten Vergleicher, um sicherzustellen, dass beim Einfügen von Elementen mit gleicher Priorität das Element mit dem höchsten Frequenzwert (dh dem niedrigsten Frequenzwert) zuerst bestellt wird.
Ich habe in meinem Blog eine vollständigere Beschreibung des Problems und seiner Lösung verfasst und einen funktionierenden C # -Code vorgestellt, der es veranschaulicht. Siehe Gleichmäßige Verteilung von Elementen in einer Liste .
Update nach Kommentaren
Ich denke, mein Problem ähnelt dem des OP, und deshalb ist meine Lösung möglicherweise nützlich. Ich entschuldige mich dafür, dass ich meine Antwort nicht mehr in Bezug auf die Frage des OP formuliert habe.
Der erste Einwand, dass meine Lösung A, B und C anstelle von 0, 1 und 2 verwendet, ist leicht zu beheben. Es ist einfach eine Frage der Nomenklatur. Ich finde es einfacher und weniger verwirrend, darüber nachzudenken und "zwei Einsen" zu sagen, anstatt "zwei Einsen". Für die Zwecke dieser Erörterung habe ich meine nachstehenden Ausgaben geändert, um die Nomenklatur des OP zu verwenden.
Natürlich beschäftigt sich mein Problem mit dem Konzept der Distanz. Wenn Sie die Dinge "gleichmäßig verteilen" möchten, ist die Entfernung impliziert. Aber auch hier war es mein Versäumnis, nicht angemessen zu zeigen, wie ähnlich mein Problem dem des OP ist.
Ich habe einige Tests mit den beiden Beispielen durchgeführt, die das OP lieferte. Das ist:
In meiner Nomenklatur werden diese als [2,2,2] bzw. [4,3,2,1] ausgedrückt. Das heißt, im letzten Beispiel "4 Elemente vom Typ 0, 3 Elemente vom Typ 1, 2 Elemente vom Typ 2 und 1 Element vom Typ 3".
Ich habe mein Testprogramm ausgeführt (wie nachstehend beschrieben) und meine Ergebnisse veröffentlicht. Ohne Eingaben aus dem OP kann ich nicht sagen, ob meine Ergebnisse ähnlich, schlechter als oder besser als seine sind. Ich kann meine Ergebnisse auch nicht mit den Ergebnissen anderer vergleichen, da noch niemand etwas veröffentlicht hat.
Ich kann jedoch sagen, dass der Algorithmus eine gute Lösung für mein Problem der Beseitigung der Schichtung beim Mischen von Flüssigkeiten darstellt. Und es sieht so aus, als ob es eine vernünftige Lösung für das OP-Problem darstellt.
Für die unten gezeigten Ergebnisse habe ich den Algorithmus verwendet, den ich in meinem Blogeintrag beschrieben habe, wobei die anfängliche Priorität auf festgelegt
Frequency/2
und der Heap-Vergleich geändert wurde, um das häufigere Element zu bevorzugen. Der geänderte Code wird hier angezeigt, wobei die geänderten Zeilen kommentiert sind.Beim Ausführen meines Testprogramms mit dem ersten Beispiel des OP erhalte ich:
Mein Algorithmus arbeitet also für das triviale Problem, dass alle Zählungen gleich sind.
Für das zweite Problem, das das OP stellte, bekam ich:
Ich sehe keinen offensichtlichen Weg, dies zu verbessern. Es könnte anders arrangiert werden, um die Abstände für Punkt 0 [2,3,2,3] oder eine andere Anordnung von 2 und 3 festzulegen, aber das ändert die Abweichungen für Punkt 1 und / oder 2. Ich weiß wirklich nicht, was "optimal" ist in dieser Situation. Ist es besser, eine größere Abweichung bei den häufigeren oder den weniger häufigen Artikeln zu haben?
Da ich keine anderen Probleme aus dem OP hatte, verwendete ich seine Beschreibungen, um einige meiner eigenen zu erfinden. Er sagte in seinem Beitrag:
Meine beiden Tests waren also:
Und meine Ergebnisse:
Und zum zweiten Beispiel:
quelle
Dies "riecht" wie es NP-schwer sein könnte. Also, was machst du, wenn du ein NP-hartes Problem hast? Werfen Sie eine Heuristik oder einen Approximationsalgorithmus oder verwenden Sie einen SAT-Solver.
Wenn Sie in Ihrem Fall nicht die absolut optimale Lösung benötigen, besteht ein vernünftiger Ausgangspunkt darin, das simulierte Tempern zu versuchen . Es gibt eine natürliche Möglichkeit, eine Kandidatenlösung zu übernehmen und in eine nahe gelegene Kandidatenlösung zu verschieben: Wählen Sie zwei Elemente in der Liste nach dem Zufallsprinzip aus und tauschen Sie sie aus. Durch simuliertes Tempern wird iterativ versucht, die Lösung zu verbessern. Sie können viele Ressourcen zum simulierten Tempern finden, wenn Sie nicht damit vertraut sind. Sie können auch mit anderen Sätzen von "lokalen Bewegungen" experimentieren, die kleine Änderungen an einer Kandidatenlösung vornehmen, mit der Hoffnung, diese schrittweise zu verbessern (dh die Standardabweichung der Entfernungen zu verringern).
Aber ich würde vorschlagen, dass Sie mit simuliertem Tempern beginnen. Das ist das erste, was ich versuchen würde, weil ich denke, es könnte einfach funktionieren.
quelle
Skizze eines heuristischen Algorithmus
Ich habe keine genaue Lösung für dieses Problem. Da Raphaels Kommentar jedoch vermuten lässt, dass es sich um das Partitionsproblem handelt, für das heuristische Algorithmen entwickelt wurden, werde ich einen heuristischen Ansatz ausprobieren. Dies ist nur eine Skizze eines heuristischen Algorithmus.
Das wird unseren Algorithmus leiten.
Es kann sich um einen Wert handeln, bei dem zunächst nur sehr wenige Vorkommen auftreten. Ich denke, es macht eigentlich keinen Unterschied, da die durch die Belegung von Slots verursachten Einschränkungen im Verhältnis zur Anzahl der gut platzierten Werte (?) Stehen.
Der erste betrachtete Wert kann ohne Einschränkung gesetzt werden. Dann müssen die anderen Werte so platziert werden, dass ihr Beitrag zur Standardabweichung minimiert wird, jedoch nur in den Slots, die durch die zuvor platzierten Werte frei bleiben.
Die Platzierung des Auftretens eines Werts in den verbleibenden Slots kann mit einem dynamischen Programmieralgorithmus erfolgen, um Berechnungen, die die gleiche Anzahl von Werten zwischen zwei Positionen platzieren, zusammenzuführen, wobei nur diejenigen beibehalten werden, die einen minimalen Beitrag zur Standardabweichung leisten (d. H Mindestwert für die Summe der Quadrate ihrer Abweichungen).
Dann setzen Sie die Singleton-Werte in die verbleibenden Slots.
Ich bin der Meinung, dass dies im Allgemeinen eine vernünftige Lösung sein sollte, aber ich habe noch keine Ahnung, wie ich es beweisen oder die Lücke mit einer optimalen Lösung abschätzen soll.
quelle
[0, 0, 0, 0, 1, 1, 1, 2, 2, 3]
und v4
zuerst Werte1
(10/3 = 3.33
, am nächsten an v), dann2
(10/2 = 5
, am nächsten) und dann0
(10/4 = 2.5
) setzen würden? Oder: Könnten Sie ein Beispiel für "abnehmende mittlere Distanzabweichung vom Wert v" geben?Es sieht so aus, als ob ich sehr spät zur Party komme, aber wenn jemand etwas posten sollte, stößt er erneut darauf. Meine Lösung ähnelt @ babou's plus. Ich hatte heute früher ein Planungsproblem in einem eingebetteten System, das mich zu diesem Thread führte. Ich habe eine Implementierung speziell für mein Problem in C, aber ich dachte, ich würde hier eine allgemeinere Lösung in Python veröffentlichen (die C-Version wird durch die Tatsache kompliziert, dass ich mich auf einen kleinen Stapel fester Größe und keinen Speicher beschränkt habe Zuweisungen, also führe ich den gesamten Algorithmus vor Ort aus). Die unten verwendete Anti-Aliasing-Technik können Sie zum Zeichnen einer Linie auf einem Bildschirm mit 2-Bit-Farbe verwenden. Der Algorithmus erzielt hier eine niedrigere Punktzahl (dh eine bessere), wenn er die Summe der Standardabweichung für die von Jim Mischel verwendeten Eingaben als diese bestimmte Lösung verwendet.
Ergebnisse für
Wenn Sie Eingaben in der von @moraes angegebenen Form vornehmen, können Sie diese in Schritten von O (n) in eine von dieser Funktion verwendbare Form umwandeln. In einer Liste mit 255 Elementen benötigen Sie nicht mehr als 255 zusätzliche Bytes, indem Sie ein paralleles Array mit den Wiederholungszählungen beibehalten. Alternativ kann ein Paar von In-Place-Sortierungen mit O (1) zusätzlichem Speicher ausgeführt werden.
PS
Bearbeiten: Ich weiß, dass diese Lösung nicht die optimale Ausgabe durch Gegenbeispiel erzeugt. Eine Eingabe von
[6, 2, 1]
Erzeugnissen[0, 1, 0, 0, 2, 0, 0, 1, 0]
; eine bessere lösung ist[0, 0, 1, 0, 2, 0, 0, 1, 0]
.quelle
Dieser Algorithmus arbeitet mit einem Array von Ganzzahlen, wobei jede Ganzzahl eine andere Kategorie darstellt. Es werden separate Arrays für jede Kategorie erstellt. Wenn das Start-Array beispielsweise [1, 1, 1, 2, 2, 3] ist, werden drei Arrays [3], [2, 2], [1, 1, 1] erstellt.
Von dort aus werden die beiden kleinsten Arrays (in diesem Beispiel [3] und [2,2]) rekursiv kombiniert und die Position der Elemente des kleineren Arrays in das zweitkleinste Array eingeteilt, hauptsächlich basierend auf dem Verhältnis der Anzahl von Vorkommen der größeren gegen die kleineren Kategorien. In diesem Beispiel würden wir mit [2,3,2] abschließen. Dann würde es dieses Array als das kleinere Array verwenden, das zu dem nächstgrößeren Array kombiniert wird, bis nur noch ein Array übrig ist.
quelle
ANSI C CODE
Dieser Code stellt sich eine gerade Linie im n-dimensionalen Raum vor (wobei n die Anzahl der Kategorien ist), die mit dem Richtungsvektor (v1, v2, ..., vi, ... vn) durch den Ursprung verläuft, wobei vi die Anzahl von ist Artikel in der Kategorie i. Ausgehend vom Ursprung ist es das Ziel, den nächstgelegenen Punkt zur Linie zu finden. Am Beispiel [0 0 0 0 0 1 1 1 2 2 2 3] ergibt sich das Ergebnis [0 1 2 0 3 1 0 2 0 1 2 0]. Mit dem Beispiel von Lungj [0 0 0 0 0 0 1 1 2] erhalten wir [0 1 0 0 2 0 0 1 0], was genau dem Ergebnis von Lungj entspricht.
Der Algorithmus wird effizienter, indem nur Ganzzahlarithmetik verwendet und nur die Deltas zwischen den Abständen von jedem Punkt zur Linie berücksichtigt werden.
# MAXKATEGORIEN definieren 100
int main () {int i = 0; int j = 0; int catsize = 0; int vector [MAXKATEGORIEN]; int point [MAXCATEGORIES]; int categories = 0; int totalitems = 0; int best = 0; lang d2 = 0L; lang vp = 0 l; lang v2 = 0L; langes Delta = 0 l; langes Beta = 0 l;
}
quelle
meine Lösung:
quelle