Thuật toán tốt để kết hợp các mục từ N danh sách vào một với phân phối cân bằng?

Question

Hãy nói rằng tôi có ba danh sách sau đây

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

012.351.

Tôi muốn kết hợp chúng thành một danh sách duy nhất, với các mục từ mỗi danh sách như phân bố đều càng tốt sorta như thế này:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

tôi m bằng cách sử dụng NET 3.5/C# nhưng tôi đang tìm kiếm thêm để làm thế nào để tiếp cận nó sau đó mã cụ thể.

EDIT: Tôi cần giữ thứ tự các phần tử từ danh sách gốc.

Answer 1

1. Lấy một bản sao danh sách có nhiều thành viên nhất. Đây sẽ là danh sách đích.

2. Sau đó, lấy danh sách có số lượng lớn nhất tiếp theo.

3. chia độ dài danh sách đích theo độ dài nhỏ hơn để cung cấp giá trị phân số lớn hơn một.

4. Đối với mỗi mục trong danh sách thứ hai, hãy duy trì bộ đếm nổi. Thêm giá trị được tính toán trong bước trước đó, và toán học làm tròn nó đến số nguyên gần nhất (giữ nguyên bộ đếm nổi ban đầu). Chèn nó vào vị trí này trong danh sách đích và tăng số lượt truy cập lên 1 để tính tiền cho nó. Lặp lại cho tất cả các thành viên trong danh sách trong danh sách thứ hai.

5. Lặp lại các bước 2-5 cho tất cả các danh sách.

EDIT: Đây có lợi thế là O (n) là tốt, đó là luôn luôn tốt đẹp :)

Answer 2

Bạn có thể chỉ cần kết hợp ba danh sách vào một danh sách duy nhất và sau đó UNSORT danh sách đó. Danh sách chưa được phân loại sẽ đạt được yêu cầu của bạn về 'phân phối đồng đều' mà không cần nỗ lực quá nhiều.

Dưới đây là triển khai unsort: http://www.vanheusden.com/unsort/.

Answer 3

Tôi đang nghĩ đến cách tiếp cận phân chia và chinh phục. Mỗi lần lặp mà bạn chia tất cả các danh sách với các phần tử> 1 thành một nửa và recurse. Khi bạn đến một điểm mà tất cả các danh sách ngoại trừ một danh sách là một phần tử, bạn có thể kết hợp chúng một cách ngẫu nhiên, bật lên một mức và kết hợp ngẫu nhiên các danh sách được xóa khỏi khung đó với chiều dài là một ... v.v.

Cái gì đó như sau đây là những gì tôi đang suy nghĩ:

- 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

Một gợi ý nhanh chóng, trong giả python-ish:

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) 

này nên phân phối các yếu tố từ danh sách ngắn hơn đồng đều hơn so với các đề xuất khác ở đây.

Answer 5

Thứ nhất, câu trả lời này là chi tiết của một con tàu tư tưởng hơn là một giải pháp concete.

OK, vì vậy bạn có danh sách 3 mục (A1, A2, A3), nơi bạn muốn A1 ở đâu đó trong 1/3 đầu tiên của danh sách đích, A2 ở 1/3 thứ hai của mục tiêu danh sách, và A3 trong 1/3 thứ ba. Tương tự như vậy bạn muốn B1 nằm trong 1/2 đầu tiên, v.v ...

Vì vậy, bạn phân bổ danh sách 10 dưới dạng mảng, sau đó bắt đầu với danh sách có nhiều mục nhất, trong trường hợp này C. Tính điểm nơi C1 nên giảm (1.5) Thả C1 ở vị trí gần nhất, (trong trường hợp này là 1 hoặc 2), sau đó tính nơi C2 sẽ giảm (3.5) và tiếp tục quá trình cho đến khi không còn Cs nữa.

Sau đó, đi kèm với danh sách có số lượng mục nhiều thứ hai. Trong trường hợp này, A. Tính nơi A1 đi (1.66), vì vậy hãy thử 2 trước. Nếu bạn đã đặt C1 ở đó, hãy thử 1. Làm tương tự cho A2 (4.66) và A3 (7.66). Cuối cùng, chúng tôi liệt kê B. B1 nên ở mức 2.5, vì vậy hãy thử 2 hoặc 3. Nếu cả hai được lấy, hãy thử 1 và 4 và tiếp tục di chuyển ra ngoài cho đến khi bạn tìm thấy một điểm trống. Làm tương tự cho B2.

Bạn sẽ kết thúc với một cái gì đó như thế này nếu bạn chọn con số thấp hơn:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

hay này nếu bạn chọn số trên:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

Điều này dường như hoạt động khá tốt đối với danh sách mẫu của bạn, nhưng tôi không biết nó sẽ mở rộng như thế nào với nhiều danh sách có nhiều mục. Hãy thử nó và cho tôi biết làm thế nào nó đi.

Answer 6

• Tạo bảng băm danh sách.
• Đối với mỗi danh sách, lưu trữ các phần tử thứ n trong danh sách dưới phím (/ n (+ (length list) 1))
• Tùy chọn, shuffle danh sách theo từng chủ chốt trong bảng băm, hoặc sắp xếp chúng theo một cách
• CONCATENATE danh sách qua các hash bởi sắp xếp chính

Answer 7

Thực hiện Andrew Rollings' câu trả lời:

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