Guter Algorithmus zum Kombinieren von Elementen aus N Listen zu einem mit ausgewogener Verteilung?

Question

Lassen Sie uns sagen, ich habe die drei folgenden Listen

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

012.351.

Ich möchte sie in einer einzigen Liste kombinieren, mit den Einzelteilen aus jeder Liste so gleichmäßig wie möglich sorta wie folgt verteilt:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

I‘ Ich benutze .NET 3.5/C#, aber ich suche mehr danach, wie man es dann spezifischen Code anwendet.

EDIT: Ich muss die Reihenfolge der Elemente aus den ursprünglichen Listen beibehalten.

Answer 1

1. Nehmen Sie eine Kopie der Liste mit den meisten Mitgliedern. Dies wird die Zielliste sein.

2. Dann nehmen Sie die Liste mit der nächstgrößten Nummer.

3. teilen Sie die Ziellistenlänge durch die kleinere Länge, um einen Bruchwert von größer als eins zu erhalten.

4. Für jedes Element in der zweiten Liste einen Float-Zähler pflegen. 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.

5. Wiederholen Sie die Schritte 2-5 für alle Listen.

EDIT: Dies hat den Vorteil, als auch O (n) sein, die :)

Answer 2

Sie könnten einfach die drei Listen in einer einzigen Liste kombinieren und dann diese Liste UNSORTIEREN. Eine unsortierte Liste sollte Ihre Anforderung an "gleichmäßig verteilt" ohne zu viel Aufwand erreichen.

Hier ist eine Implementierung von unsor: http://www.vanheusden.com/unsort/.

Answer 3

Ich denke an einen Teil-und-herrsche-Ansatz. Jede Iteration, von der Sie alle Listen mit Elementen> 1 halbiert und rekursiv sind. Wenn Sie an einen Punkt kommen, an dem alle Listen außer einem Element ein Element enthalten, können Sie diese zufällig kombinieren, eine Ebene aufklappen und die Listen, die aus dem Rahmen entfernt wurden, in dem die Länge eins war, zufällig kombinieren ... und so weiter.

So etwas wie die folgende ist, was ich denke:

- filter lists into three categories 
    - lists of length 1 
    - first half of the elements of lists with > 1 elements 
    - second half of the elements of lists with > 1 elements 
- recurse on the first and second half of the lists if they have > 1 element 
    - combine results of above computation in order 
- randomly combine the list of singletons into returned list 

Answer 4

Ein kurzer Vorschlag, in Python-ish Pseudo-Code:

merge = list() 
lists = list(list_a, list_b, list_c) 
lists.sort_by(length, descending) 

while lists is not empty: 
    l = lists.remove_first() 
    merge.append(l.remove_first()) 
    if l is not empty: 
     next = lists.remove_first() 
     lists.append(l) 
     lists.sort_by(length, descending) 
     lists.prepend(next) 

Diese Elemente aus kürzeren Listen gleichmäßiger als die verteilen sollte andere Vorschläge hier.

Answer 5

Zuerst ist immer schön, diese Antwort ist eher ein Gedankengang als eine concete Lösung.

OK, Sie haben also eine Liste von 3 Elementen (A1, A2, A3), wo A1 in der ersten 1/3 der Zielliste, A2 in der zweiten 1/3 des Ziels sein soll Liste und A3 im dritten 1/3. Ebenso möchten Sie B1 in der ersten 1/2, usw. sein ...

Also Sie Ihre Liste von 10 als Array zuordnen, dann beginnen Sie mit der Liste mit den meisten Elementen, in diesem Fall C. Berechnen Sie den Punkt Wo 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 C 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 bei 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. Machen Sie das Gleiche für B2.

Sie werden mit etwas so enden, wenn Sie die untere Nummer wählen:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

oder dies, falls Sie die obere Nummer wählen:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

Dies 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.

Answer 6

• Erstellen Sie eine Hashtabelle mit Listen.
• Für jede Liste, speichern Sie das n-te Element in der Liste unter dem Schlüssel (/ n (+ (length list) 1))
• Optional mischt die Listen unter jedem Schlüssel in der Hash-Tabelle, oder sie in der Hash in irgendeine Weise
• Concatenate die Listen sortieren Schlüssel

Answer 7

Implementierung von Andrew Rollings sortiert Antwort:

public List<String> equimix(List<List<String>> input) { 

    // sort biggest list to smallest list 
    Collections.sort(input, new Comparator<List<String>>() { 
    public int compare(List<String> a1, List<String> a2) { 
     return a2.size() - a1.size(); 
    } 
    }); 

    List<String> output = input.get(0); 

    for (int i = 1; i < input.size(); i++) { 
    output = equimix(output, input.get(i)); 
    } 

    return output; 
} 

public List<String> equimix(List<String> listA, List<String> listB) { 

    if (listB.size() > listA.size()) { 
    List<String> temp; 
    temp = listB; 
    listB = listA; 
    listA = temp; 
    } 

    List<String> output = listA; 

    double shiftCoeff = (double) listA.size()/listB.size(); 
    double floatCounter = shiftCoeff; 

    for (String item : listB) { 
    int insertionIndex = (int) Math.round(floatCounter); 
    output.add(insertionIndex, item); 
    floatCounter += (1+shiftCoeff); 
    } 

    return output; 
}