Dobry algorytm łączenia elementów z list N w taki ze zrównoważoną dystrybucją?

Question

Załóżmy, że ma trzy następujące listy

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

chciałbym je połączyć w jedną listę, z elementami z każdej listy jako równomiernie rozłożonych możliwie coś w stylu tego:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

I m przy użyciu .NET 3.5/C#, ale szukam więcej, jak do niego podejść, a następnie konkretnego kodu.

EDYCJA: Muszę zachować kolejność elementów z oryginalnych list.

Answer 1

1. Zrób kopię listy z największą liczbą członków. To będzie lista docelowa.

2. Następnie wybierz listę z kolejnym największym numerem.

3. podzielić długość listy miejsc docelowych na mniejszą długość, aby uzyskać wartość ułamkową większą niż jeden.

4. Dla każdej pozycji z drugiej listy należy zachować licznik swobodnych ruchów. Dodaj wartość obliczoną w poprzednim kroku i matycznie zaokrąglij ją do najbliższej liczby całkowitej (zachowaj nienaruszony oryginalny licznik pływalności). Wstaw ją w tej pozycji na liście docelowej i zwiększ jej licznik o 1, aby to uwzględnić. Powtórz dla wszystkich członków listy na drugiej liście.

5. Powtórz kroki 2-5 dla wszystkich list.

EDIT: Ma to tę zaletę, że jest O (n), a także, co jest zawsze miły :)

Answer 2

Można po prostu połączyć trzy listy w jedną listę, a następnie UNORTUJ tę listę. Lista nieposortowana powinna osiągnąć twoje wymaganie "równomiernie rozprowadzonego" bez zbytniego wysiłku.

Oto implementacja odrzucenia: http://www.vanheusden.com/unsort/.

Answer 3

Mam na myśli podejście polegające na podziale i podboju. Każda iteracja, z której dzielisz wszystkie listy, zawiera elementy> 1 na pół i rekurencyjne. Gdy dojdziesz do punktu, w którym wszystkie listy oprócz jednego są jednym elementem, możesz je losowo połączyć, wyskoczyć na wyższy poziom i losowo połączyć listy usunięte z tej ramki, gdzie długość wynosi jeden ... et cetera.

Coś po to, co mam na myśli:

- 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

Szybka sugestia, w python-owski Pseudokod:

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) 

ten powinien rozprowadzać elementy z krótszych list bardziej równomiernie niż inne sugestie tutaj.

Answer 5

Po pierwsze, ta odpowiedź jest raczej tok myślenia niż rozwiązanie concete.

OK, więc masz listę 3 przedmiotów (A1, A2, A3), gdzie chcesz, aby A1 znajdowało się gdzieś na pierwszej 1/3 listy celów, A2 w drugiej 1/3 celu lista i A3 w trzeciej 1/3. Tak samo chcesz, aby B1 był w pierwszej 1/2, itd ...

Przypisujesz swoją listę 10 jako tablicę, a następnie zaczynasz od listy zawierającej najwięcej elementów, w tym przypadku C. Oblicz miejsce gdzie C1 powinien spaść (1.5) Upuść C1 w najbliższym miejscu (w tym przypadku 1 lub 2), a następnie obliczyć, gdzie powinna spaść C2 (3.5) i kontynuować proces, dopóki nie będzie już więcej Cs.

Następnie przejdź do listy z drugą do największej liczby pozycji. W tym przypadku A. Oblicz, gdzie A1 idzie (1,66), więc spróbuj najpierw 2. Jeśli już umieściłeś tam C1, spróbuj 1. Zrób to samo dla A2 (4.66) i A3 (7.66). Na koniec tworzymy listę B. B1 powinna wynosić 2,5, więc spróbuj 2 lub 3. Jeśli obie są zajęte, spróbuj 1 i 4 i idź dalej, aż znajdziesz puste miejsce. Zrób to samo dla B2.

Będziesz skończyć z czymś takim, jeśli wybrać niższy numer:

C1 A1 A2 C2 C3 C4 A3 B1 B2 C5

czy to jeśli wybierzesz numer górna:

A1 C1 B1 C2 A3 C3 A3 C4 B2 C5

Wydaje się, że działa to całkiem dobrze na liście próbek, ale nie wiem, jak dobrze będzie skalować się do wielu list z wieloma pozycjami. Spróbuj i daj mi znać, jak to działa.

Answer 6

• Sporządź tabelę skrótów list.
• Dla każdej listy, przechowywać n-ty element listy pod klucz (/ n (+ (length list) 1))
• Opcjonalnie shuffle list pod każdym kluczem w tabeli mieszania lub sortować je w jakiś sposób
• złączyć wykazy w hashującej klasyfikowane kluczową

Answer 7

Realizacja Andrew Rollings' odpowiedź:

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; 
}