algorithm - programa - php combinaciones sin repeticion

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

Question

Digamos que tengo las 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 de la manera más parecida posible, así:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

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

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

Answer 1

Primero, esta respuesta es más una línea de pensamiento que una solución de conceto.

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 de la lista de objetivos y A3 en el tercero 1/3. Del mismo modo, quieres que B1 esté en el primer 1/2, etc.

Asigne su lista de 10 como una matriz, luego comience con la lista con la mayor cantidad de elementos, en este caso C. Calcule el lugar donde C1 debería caer (1.5) Caiga C1 en el lugar más cercano (en este caso, ya sea 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 con la lista con el segundo al mayor 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.

Si escoges el número más bajo terminarás con algo como esto:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

o esto si eliges el número superior:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

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

Answer 2

Simplemente podría 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

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

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

Answer 4

• Haz una tabla hash de listas.
• Para cada lista, almacene el enésimo elemento en la lista debajo de la tecla (/ n (+ (length list) 1))
• Opcionalmente, mezcle las listas debajo de cada tecla en la tabla hash, u ordénelas de algún modo
• Concatenar las listas en el hash por clave ordenada

Answer 5

Estoy pensando en un enfoque de 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 estoy pensando:

- 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 6

1. Tome una copia de la lista con la mayoría de los 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 en la segunda lista, mantenga un contador flotante. 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.

EDITAR: Esto tiene la ventaja de ser O (n) también, lo cual siempre es bueno :)

Answer 7

Implementación de la respuesta de Andrew Rollings:

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