¿Buen algoritmo para combinar elementos de N listas en uno con distribución equilibrada?

Question

Digamos que tengo los tres siguientes listas

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

me gustaría combinarlos en una sola lista, con los elementos de cada lista distribuidos lo más uniformemente posible sorta como esto:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

I' Estoy usando .NET 3.5/C# pero estoy buscando más información sobre cómo abordarlo y luego el código específico.

EDITAR: Necesito mantener el orden de los elementos de las listas originales.

Answer 1

1. Obtenga una copia de la lista con más miembros. Esta será la lista de destinos.

2. Luego tome la lista con el siguiente número más grande.

3. divida la longitud de la lista de destinos por la menor longitud para obtener un valor fraccionario mayor que uno.

4. Para cada elemento de la segunda lista, mantenga un contador de flotación. Agregue el valor calculado en el paso anterior y matemáticamente redondéelo al número entero más cercano (mantenga intacto el flotador original). Insértelo en esta posición en la lista de destinos e incremente el contador en 1 para dar cuenta de ello. Repita para todos los miembros de la lista en la segunda lista.

5. Repita los pasos 2 a 5 para todas las listas.

EDIT: Esto tiene la ventaja de ser O (n), así, que siempre es agradable :)

Answer 2

Simplemente puede combinar las tres listas en una sola lista y luego DESHACER esa lista. Una lista sin clasificar debe cumplir con su requisito de "distribución uniforme" sin demasiado esfuerzo.

Aquí hay una implementación de unsort: http://www.vanheusden.com/unsort/.

Answer 3

Estoy pensando en un enfoque dividir y conquistar. Cada iteración de la cual divide todas las listas con elementos> 1 en la mitad y recurse. Cuando llegue a un punto en el que todas las listas, excepto una, sean de un elemento, puede combinarlas aleatoriamente, despliegue un nivel y combine aleatoriamente las listas eliminadas de ese marco donde la longitud fue de una ... etcétera.

algo como lo siguiente es lo que pienso:

- 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

Una sugerencia rápida, en pseudocódigo pitón-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) 

Esto debería distribuir los elementos de las listas cortas de manera más uniforme que la otras sugerencias aquí.

Answer 5

En primer lugar, esta respuesta es más bien una línea de pensamiento que una solución concete.

OK, entonces tiene una lista de 3 elementos (A1, A2, A3), donde quiere que A1 esté en algún lugar en el primer 1/3 de la lista de objetivos, A2 en el segundo 1/3 del objetivo lista, y A3 en el tercero 1/3. Del mismo modo, quiere que B1 esté en la primera 1/2, etc.

Asigna su lista de 10 como una matriz y luego comience con la lista con la mayor cantidad de elementos, en este caso C. Calcule la mancha donde C1 debería caer (1.5) Caiga C1 en el lugar más cercano, (en este caso, 1 o 2), luego calcule dónde C2 debería caer (3.5) y continúe el proceso hasta que no haya más Cs.

Luego vaya a la lista con el segundo número de artículos. En este caso, A. Calcule hacia dónde va A1 (1.66), así que intente con 2 primero. Si ya has puesto C1 allí, prueba 1. Haz lo mismo con A2 (4.66) y A3 (7.66). Finalmente, hacemos una lista de B. B1 debería ir a 2.5, así que pruebe con 2 o 3. Si se toman ambos, intente con 1 y 4 y siga moviéndose radialmente hasta que encuentre un punto vacío. Haz lo mismo con B2.

Usted va a terminar con algo como esto si tienes que elegir el número más bajo:

C1 A1 A2 C2 C3 C4 A3 B1 B2 C5

o esto si tienes que elegir el número más alto:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

Esto parece funcionar bastante bien para sus listas de muestras, pero no sé qué tan bien se escalará a muchas listas con muchos artículos. Pruébalo y cuéntame cómo funciona.

Answer 6

• Haga una tabla hash de listas.
• Para cada lista, guardar el enésimo elemento en la lista bajo la clave (/ n (+ (length list) 1))
• Opcionalmente, barajar las listas en cada tecla en la tabla hash, o clasificarlos de alguna manera
• Concatenar las listas en el hash de ordenados clave

Answer 7

Implementación de Andrew Rollings' respuesta:

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