Algorithmus zum Trennen von Objekten desselben Typs

Ich habe eine Liste von Elementen, jedes mit einem Typ identifiziert, ich muss die Liste neu anordnen, um den Mindestabstand zwischen Elementen des gleichen Typs zu maximieren .

Das Set ist klein (10 bis 30 Stück), performance ist nicht wirklich wichtig.

Die Anzahl der Artikel pro Typ oder Anzahl der Typen ist unbegrenzt, die Daten können als zufällig betrachtet werden.

Zum Beispiel, wenn ich eine Liste habe von:

  • 5 Artikel von A
  • 3 Artikel von B
  • 2 Stücke von C
  • 2 Stücke von D
  • 1 Stück von E
  • 1 Artikel von F

Ich möchte etwas wie A , B , C , A , D , F , B , A , E , C , A , D , B , A

  • A hat mindestens 2 Einträge zwischen Vorkommen
  • B hat mindestens 4 Einträge zwischen Vorkommen
  • C hat 6 Einträge zwischen Vorkommen
  • D hat 6 Gegenstände zwischen Vorkommen

Gibt es einen Algorithmus, um dies zu erreichen?

-Aktualisieren-

Nachdem ich einige Kommentare ausgetauscht hatte, kam ich zu einer Definition eines sekundären Ziels:

  • Hauptziel : Maximierung des Mindestabstandes zwischen Elementen des gleichen Typs, wobei nur die Art (en) mit weniger Abstand berücksichtigt werden.
  • Zweites Ziel : Maximieren Sie den Mindestabstand zwischen Elementen auf jedem Typ. IE: Wenn eine Kombination den Mindestabstand eines bestimmten Typs erhöht, ohne den anderen zu verringern, wählen Sie ihn aus.

-Update 2-

Über die Antworten. Es gab viele nützliche Antworten, obwohl keine eine Lösung für beide Ziele ist, besonders die zweite, die schwierig ist.

Einige Gedanken über die Antworten:

  • PengOne : Klingt gut, bietet aber keine konkrete Umsetzung und führt nicht immer zum besten Ergebnis nach dem zweiten Ziel.
  • Evgeny Kluev : Bietet eine konkrete Umsetzung zum Hauptziel, führt aber nicht zum besten Ergebnis im Sinne des Nebenziels.
  • tobias_k: Ich mag den zufälligen Ansatz, es führt nicht immer zum besten Ergebnis, aber es ist eine gute Annäherung und kosteneffektiv.

Ich habe eine Kombination aus Evgeny Kluev, Backtracking und tobias_k Formel ausprobiert, aber es brauchte zu viel Zeit, um das Ergebnis zu erhalten.

Schließlich, zumindest für mein Problem, hielt ich tobias_k für den am besten geeigneten Algorithmus, für seine Einfachheit und gute Ergebnisse in einer zeitgerechten Weise. Wahrscheinlich könnte es mit Simulated Annealing verbessert werden.

Das klang nach einem interessanten Problem, also habe ich es einfach versucht. Hier ist mein super vereinfachter randomisierter Ansatz, der in Python gemacht wurde:

 def optimize(items, quality_function, stop=1000): no_improvement = 0 best = 0 while no_improvement < stop: i = random.randint(0, len(items)-1) j = random.randint(0, len(items)-1) copy = items[::] copy[i], copy[j] = copy[j], copy[i] q = quality_function(copy) if q > best: items, best = copy, q no_improvement = 0 else: no_improvement += 1 return items 

Wie bereits in den Kommentaren besprochen, ist der wirklich knifflige Teil die Qualitätsfunktion, die als Parameter an den Optimierer übergeben wird. Nach einigen Versuchen kam ich auf eine, die fast immer optimale Ergebnisse liefert. Danke an pmoleri , dass Sie darauf hingewiesen haben, wie Sie das Ganze noch effizienter machen können.

 def quality_maxmindist(items): s = 0 for item in set(items): indcs = [i for i in range(len(items)) if items[i] == item] if len(indcs) > 1: s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1)) return 1./s 

Und hier ein zufälliges Ergebnis:

 >>> print optimize(items, quality_maxmindist) ['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A'] 

Beachten Sie, dass derselbe Optimierer, wenn er eine andere Qualitätsfunktion übergibt, für verschiedene Listenumordnungsaufgaben verwendet werden könnte, z. B. als (ziemlich alberner) randomisierter Sortierer.

Erstens haben Sie noch kein gut definiertes Optimierungsproblem. Wenn Sie den Mindestabstand zwischen zwei Objekten desselben Typs maximieren möchten, ist dies gut definiert. Wenn Sie den minimalen Abstand zwischen zwei A’s und zwischen zwei B’s und … und zwischen zwei Z’s maximieren wollen, dann ist das nicht gut definiert. Wie würden Sie zwei Lösungen vergleichen:

  1. A’s sind mindestens 4 voneinander entfernt, B ist mindestens 4 getrennt und C ist mindestens 2 auseinander
  2. A ist mindestens 3 auseinander, B ist mindestens 3 auseinander, und C ist mindestens 4 auseinander

Sie brauchen ein genau definiertes Maß von “gut” (oder besser “besser”). Ich nehme für jetzt an, dass das Maß ist: Maximiere den minimalen Abstand zwischen irgendwelchen zwei des gleichen Einzelteils .

Hier ist ein Algorithmus, der eine Mindestdistanz erreicht ceiling(N/n(A)) wobei N die Gesamtzahl der Elemente und n(A) die Anzahl der Elemente der Instanz A , unter der Annahme, dass A am zahlreichsten ist.

  • Ordne die Elementtypen A1, A2, ... , Ak mit n(Ai) >= n(A{i+1}) .
  • Initialisiere die Liste L , um leer zu sein.
  • Für j von k bis 1 , verteile Objekte vom Typ Ak so gleichmäßig wie möglich in L

Beispiel: Wenn die Verteilung in der Frage gegeben ist, erzeugt der Algorithmus:

 F E, F D, E, D, F D, C, E, D, C, F B, D, C, E, B, D, C, F, B A, B, D, A, C, E, A, B, D, A, C, F, A, B 

Hier ist ein Algorithmus, der nur den minimalen Abstand zwischen Elementen des gleichen Typs maximiert und nichts darüber hinaus tut. Die folgende Liste dient als Beispiel:

 AAAAA BBBBB CCCC DDDD EEEE FFF GG 
  • Sortiert Elementmengen nach Anzahl der Elemente jedes Typs in absteigender Reihenfolge. Eigentlich sollten nur die größten Mengen (A & B) an den Anfang der Liste gesetzt werden, genauso wie diejenigen Elementmengen, die ein Element weniger haben (C & D & E). Andere Sätze können unsortiert sein.
  • Reserviere die letzten Positionen in dem Array für ein Element von jedem der größten Sätze, teile das verbleibende Feld gleichmäßig zwischen den S-1 verbleibenden Elementen der größten Sätze. Dies ergibt einen optimalen Abstand: K = (N – R) / (S – 1). Darstellen Ziel-Array als eine 2D-Matrix mit K-Spalten und L = N / K vollständige Zeilen (und möglicherweise eine Teilzeile mit N% K-Elementen). Zum Beispiel haben wir R = 2, S = 5, N = 27, K = 6, L = 4.
  • Wenn die Matrix S – 1 vollständige Zeilen hat, füllen Sie die ersten R – Spalten dieser Matrix mit Elementen der größten Mengen (A und B), andernfalls füllen Sie alle Spalten nacheinander, beginnend mit der letzten.

Für unser Beispiel gibt dies:

 AB.... AB.... AB.... AB.... AB. 

Wenn wir versuchen, die verbleibenden Spalten mit anderen Mengen in derselben Reihenfolge zu füllen, gibt es ein Problem:

 ABCDE. ABCDE. ABCDE. ABCE.. ABD 

Das letzte ‘E’ ist nur 5 Positionen vom ersten ‘E’ entfernt.

  • Sequentiell füllen Sie alle Spalten beginnend mit der letzten.

Für unser Beispiel gibt dies:

 ABFEDC ABFEDC ABFEDC ABGEDC ABG 

Zurück zum linearen Array haben wir:

 ABFEDCABFEDCABFEDCABGEDCABG 

Hier ist ein Versuch, Simulated Annealing für dieses Problem (C-Quellen) zu verwenden: http://ideone.com/OGkkc .

Ich glaube, du könntest dein Problem wie eine Ansammlung von Partikeln sehen, die sich physisch gegenseitig abstoßen. Sie könnten zu einer “stabilen” Situation übergehen.

Grundlegender Pseudo-Code:

 force( x, y ) = 0 if x.type==y.type 1/distance(x,y) otherwise nextposition( x, force ) = coined?(x) => same else => x + force notconverged(row,newrow) = // simplistically row!=newrow row=[a,b,a,b,b,b,a,e]; newrow=nextposition(row); while( notconverged(row,newrow) ) newrow=nextposition(row); 

Ich weiß nicht, ob es konvergiert, aber es ist eine Idee 🙂

Ich bin mir sicher, dass es eine effizientere Lösung gibt, aber hier ist eine Möglichkeit für Sie:

Beachten Sie zunächst, dass es sehr einfach ist, eine Reihenfolge zu finden, die einen Mindestabstand zwischen den gleichen Artikeln von 1 ergibt. Verwenden Sie einfach eine beliebige Reihenfolge, und der MDBIOST wird mindestens 1, wenn nicht mehr.

Beginnen Sie also mit der Annahme, dass der MDBIOST 2 sein wird. Führen Sie eine rekursive Suche im Raum möglicher Ordnungen durch, basierend auf der Annahme, dass MDBIOST 2 ist . Es gibt eine Reihe von Bedingungen, die Sie verwenden können, um Zweige von dieser Suche zu entfernen. Beenden Sie die Suche, wenn Sie eine funktionierende Bestellung finden.

Wenn Sie einen gefunden haben, der funktioniert, versuchen Sie es erneut unter der Annahme, dass MDBIOST 3 ist. Dann 4 … und so weiter, bis die Suche fehlschlägt.

UPDATE: Es wäre eigentlich besser, mit einer hohen Zahl zu beginnen, weil das die möglichen Entscheidungen mehr einschränkt. Dann reduzieren Sie die Anzahl schrittweise, bis Sie eine Ordnung finden, die funktioniert.

Hier ist ein anderer Ansatz.

Wenn jeder Gegenstand mindestens k Plätze von jedem anderen Gegenstand des gleichen Typs behalten muss, notieren Sie die Gegenstände von links nach rechts und behalten Sie die Anzahl der übriggebliebenen Gegenstände jedes Typs im Auge. Platziere an jedem Punkt einen Gegenstand mit der größten Anzahl, die du legal legst.

Dies funktioniert für N Items, wenn es nicht mehr als ceil (N / k) Items des gleichen Typs gibt, da diese Eigenschaft erhalten bleibt – nach dem Ablegen von k Items haben wir k weniger Items und wir haben mindestens einen von jeder Typ, der mit einem Stück (N / k) dieses Typs begonnen hat.

Bei einer Kombination von gemischten Gegenständen könntest du das größte k ausarbeiten, das du unterstützen kannst, und dann die Gegenstände auslegen, um dieses k zu lösen.