Nehmen wir an, ich habe die folgenden drei Listen
A1
A2
A3
B1
B2
C1
C2
C3
C4
C5
Ich möchte sie in einer einzigen Liste zusammenfassen, wobei die Elemente aus jeder Liste so gleichmäßig wie möglich verteilt sind:
C1
A1
C2
B1
C3
A2
C4
B2
A3
C5
Ich benutze .NET 3.5 / C #, aber ich suche mehr danach, wie man dann spezifischen Code anwendet.
EDIT: Ich muss die Reihenfolge der Elemente aus den ursprünglichen Listen beibehalten.
Nehmen Sie eine Kopie der Liste mit den meisten Mitgliedern. Dies wird die Zielliste sein.
Dann nimm die Liste mit der nächstgrößeren Nummer.
Teilen Sie die Ziellistenlänge durch die kleinere Länge, um einen Bruchwert von größer als eins zu erhalten.
Pflegen Sie für jedes Element in der zweiten Liste einen Float-Zähler. Fügen Sie den im vorherigen Schritt berechneten Wert hinzu und runden Sie ihn mathematisch auf die nächste ganze Zahl ab (lassen Sie den ursprünglichen Float-Zähler unverändert). Fügen Sie ihn an dieser Position in die Zielliste ein und erhöhen Sie den Zähler um 1, um ihn zu berücksichtigen. Wiederholen Sie dies für alle Listenmitglieder in der zweiten Liste.
Wiederholen Sie die Schritte 2-5 für alle Listen.
EDIT: Das hat den Vorteil, auch O (n) zu sein, was immer nett ist:)
Erstens ist diese Antwort eher ein Gedankengang als eine konzeptuelle Lösung.
OK, Sie haben also eine Liste von 3 Elementen (A1, A2, A3), wobei A1 irgendwo im ersten Drittel der Zielliste, A2 im zweiten Drittel der Zielliste stehen soll und A3 im dritten Drittel. Ebenso möchtest du, dass B1 in der ersten 1/2 ist, usw. ...
Sie ordnen also Ihre Liste von 10 als ein Array zu, dann beginnen Sie mit der Liste mit den meisten Elementen, in diesem Fall C. Berechnen Sie die Stelle, an der C1 fallen sollte (1.5) C1 am nächsten Punkt fallen lassen (in diesem Fall) , entweder 1 oder 2), dann berechnen, wo C2 fallen sollte (3.5) und den Prozess fortsetzen, bis es keine Cs mehr gibt.
Dann gehen Sie mit der Liste mit der zweithöchsten Anzahl von Elementen. In diesem Fall A. Berechnen Sie, wo A1 geht (1.66), also versuchen Sie es zuerst mit 2. Wenn Sie C1 bereits dort eingeben, versuchen Sie 1. Tun Sie dasselbe für A2 (4.66) und A3 (7.66). Zum Schluss listen wir B auf. B1 sollte auf 2,5 gehen, also versuchen Sie es mit 2 oder 3. Wenn beide genommen werden, versuchen Sie 1 und 4 und bewegen Sie sich weiter radial nach außen, bis Sie eine leere Stelle finden. Tun Sie dasselbe für B2.
Wenn Sie die niedrigere Zahl wählen, erhalten Sie so etwas wie folgt:
C1 A1 C2 A2 C3 B1 C4 A3 C5 B2
oder wenn Sie die obere Zahl auswählen:
A1 C1 B1 C2 A2 C3 A3 C4 B2 C5
Das scheint für Ihre Beispiellisten ziemlich gut zu funktionieren, aber ich weiß nicht, wie gut es auf viele Listen mit vielen Elementen skalieren wird. Probieren Sie es aus und lassen Sie mich wissen, wie es geht.
(/ n (+ (length list) 1))
Ich denke an einen "teile und herrsche" -Ansatz. Jede Iteration, in die Sie alle Listen mit Elementen & gt; 1 in der Hälfte und recurse. Wenn Sie zu einem Punkt kommen, an dem alle Listen außer einem Element zu einem Element gehören, können Sie diese zufällig kombinieren, eine Ebene aufklappen und die Listen, die aus dem Rahmen mit der Länge 1 entfernt wurden, beliebig kombinieren ... und so weiter.
Etwas wie das Folgende ist, was ich denke:
%Vor%Sie könnten einfach die drei Listen zu einer einzigen Liste kombinieren und dann diese Liste UNSORTIEREN. Eine unsortierte Liste sollte Ihre Anforderung von "gleichmäßig verteilt" ohne zu viel Aufwand erreichen.
Hier ist eine Implementierung von unsort: Ссылка .