Algoritmo para fusionar dos listas que carecen de comparación entre ellas

Question

Estoy buscando un algoritmo para unir dos listas ordenadas, pero les falta un operador de comparación entre los elementos de una lista y los elementos de la otra. La lista combinada resultante puede no ser única, pero cualquier resultado que satisfaga el orden de clasificación relativo de cada lista servirá. Más precisamente:

Dado:

• Listas A = {a_1, ..., a_m}, y B = {b_1, ..., b_n}. (También pueden considerarse conjuntos).
• Un operador de precedencia < definido entre los elementos de cada lista de tal manera que a_i < a_{i+1}, y b_j < b_{j+1} para 1 <= i <= m y 1 <= j <= n.
• El operador de precedencia no está definido entre los elementos de A y B: a_i < b_j no está definido para ningún i válido y j.
• Un operador de igualdad = definido entre todos los elementos de A o B (se define entre un elemento de A y un elemento de B).
• No hay dos elementos de la lista A son iguales, y lo mismo vale para la lista B.

Produce: Una lista C = {c_1, ..., c_r} tal que:

• C = union(A, B); los elementos de C son la unión de elementos de A y B.
• Si c_p = a_i, c_q = a_j y a_i < a_j, entonces c_p < c_q. (El orden de los elementos de las sublistas de C correspondientes a los conjuntos A y B debe ser preservada.
• no existen i y j tal que c_i = c_j. (todos los elementos duplicados entre A y B se eliminan).

espero que esta pregunta tiene sentido y que no estoy pidiendo algo, ya sea terriblemente obvio, o algo para lo que no existe una solución

Contexto:.

Un número realizable se puede representar exactamente en finitas muchas extensiones cuadráticas en el campo de números racionales (utilizando un árbol binario de altura igual al número de extensiones de campo). Por lo tanto, una representación de un número que se puede construir debe "conocer" el campo en el que se representa. Las listas A y B representan sucesiones cuadráticas sucesivas de los números racionales. Los elementos de A y B en sí mismos son números que se pueden construir, que se definen en el contexto de campos más pequeños anteriores (de ahí el operador de precedencia).Al agregar/multiplicar números que se pueden construir, , los campos extendidos cuadráticamente deben fusionarse primero para que se puedan realizar las operaciones aritméticas binarias ; la lista resultante C es el campo cuadráticamente extendido que puede representar números representables por ambos campos A y B. (Si alguien tiene una mejor idea de cómo trabajar programáticamente con números que se pueden construir, hágamelo saber. Una pregunta sobre números constructivos tiene arisen before , y también aquí hay algunos interesting responses sobre su representación.)

Antes de que nadie pregunte, no, esta pregunta no pertenece a mathoverflow; odian las preguntas de algoritmo (y generalmente no de nivel de postgrado).

En la práctica, las listas A y B son listas vinculadas (en realidad, almacenadas en orden inverso). También necesitaré hacer un seguimiento de los elementos de C que corresponden a A y B, pero ese es un detalle menor. El algoritmo que busco no es la operación de combinación en mergesort, porque el operador de precedencia no está definido entre los elementos de las dos listas que se fusionan. Todo finalmente se implementará en C++ (solo quiero que el operador se sobrecargue). Esto no es tarea, y eventualmente será de fuente abierta, FWIW.

Answer 1

Yo no piensa puede hacerlo mejor que O (N * M), aunque estaría feliz de estar equivocado.

Siendo ese el caso, me gustaría hacer esto:

• Tome el primer elemento (restante) de A.
• buscarlo en (lo que queda de) B.
  • Si no lo encuentra en B, muévalo a la salida
  • Si lo encuentra en B, mueva todo de B hasta incluir la coincidencia y suelte la copia de A.
• Repetir lo anterior hasta que A está vacía
• mover nada queda en B a la salida

Si desea detectar ordenamientos incompatibles de A y B, a continuación, quitar "(lo que queda de)" desde el paso 2. Busque el total de B y genere un error si lo encuentra "demasiado pronto".

El problema es que dado un elemento general de A, no hay forma de buscarlo en B en un tiempo mejor que el lineal (en el tamaño de B), porque todo lo que tenemos es una prueba de igualdad. Pero es evidente que tenemos que encontrar los partidos de alguna manera y (aquí es donde agito un poco las manos, no puedo demostrarlo de inmediato), por lo tanto, tenemos que verificar cada elemento de A para la contención en B. Podemos evitar un montón de comparaciones porque las órdenes de los dos conjuntos son consistentes (al menos, supongo que sí, y si no, no hay solución).

Por lo tanto, en el peor caso la intersección de las listas está vacía, y no hay elementos de A son orden comparable con cualquier elementos de B. Esto requiere tests de igualdad * M N para establecer, de ahí el peor de los casos ligado.

Para su problema de ejemplo A = (1, 2, c, 4, 5, f), B = (a, b, c, d, e, f), esto da el resultado (1,2, a , b, c, 4,5, d, e, f), lo cual me parece bien. Realiza 24 pruebas de igualdad en el proceso (a menos que no pueda contar): 6 + 6 + 3 + 3 + 3 + 3. Fusionarse con A y B a la inversa produciría (a, b, 1,2, c , d, e, 4,5, f), en este caso con el mismo número de comparaciones, ya que los elementos coincidentes simplemente están en índices iguales en las dos listas.

Como puede verse en el ejemplo, la operación no se puede repetir. merge (A, B) da como resultado una lista con un orden incoherente con el de fusión (B, A). Por lo tanto, fusionar ((fusión (A, B), fusión (B, A)) no está definido. En general, el resultado de una fusión es arbitrario, y si utiliza órdenes arbitrarias como base de nuevas órdenes completas, lo hará generar órdenes mutuamente incompatibles.

Answer 2

Parece que usaría una forma degenerada de clasificación topológica.

EDIT 2:

Ahora con una rutina combinada:

import itertools 

list1 = [1, 2, 'c', 4, 5, 'f', 7] 
list2 = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 

ibase = 0 
result = [] 

for n1, i1 in enumerate(list1): 
    for n2, i2 in enumerate(itertools.islice(list2, ibase, None, 1)): 
    if i1 == i2: 
     result.extend(itertools.islice(list2, ibase, ibase + n2)) 
     result.append(i2) 
     ibase = n2 + ibase + 1 
     break 
    else: 
    result.append(i1) 
result.extend(itertools.islice(list2, ibase, None, 1)) 

print result 

Answer 3

Would concatenando las dos listas son suficientes? Mantiene la clasificación relativa de los elementos de a y los elementos de b.

Luego, solo es cuestión de eliminar duplicados.

EDIT: Muy bien, después de que el comentario de discusión (y dada la condición adicional de que a_i=b_i & a_j=b_j & a_i<a_j => b_i<b-J), aquí es una solución razonable:

1. identificar las entradas comunes a las listas. Esto es O (n) para el algoritmo ingenuo: es posible que pueda mejorarlo.

2. (opcional) verifique que las entradas comunes estén en el mismo orden en ambas listas.

3. Construya la lista de resultados: todos los elementos de a que están antes del primer elemento compartido, seguidos de todos los elementos de b antes del primer elemento compartido, seguido del primer elemento compartido, y así sucesivamente.

Answer 4

Dado el problema tal como lo ha expresado, tengo la sensación de que el problema puede no tener solución. Suponga que tiene dos pares de elementos {a_1, b_1} y {a_2, b_2} donde a_1 < a_2 en el pedido de A, y b_1 > b_2 en el pedido de B. Ahora suponga que a_1 = b_1 y a_2 = b_2 de acuerdo con el operador de igualdad para A y B. En este escenario, no lo hago Creo que puede crear una lista combinada que satisfaga el requisito de orden de la sublista.

De todos modos, hay un algoritmo que debería hacer el truco. (Codificado en Java-ish ...)

List<A> alist = ... 
List<B> blist = ... 
List<Object> mergedList = new SomeList<Object>(alist); 
int mergePos = 0; 
for (B b : blist) { 
    boolean found = false; 
    for (int i = mergePos; i < mergedList.size(); i++) { 
     if (equals(mergedList.get(i), b)) { 
      found = true; break; 
     } 
    } 
    if (!found) { 
     mergedList.insertBefore(b, mergePos); 
     mergePos++; 
    } 
} 

Este algoritmo es O(N**2) en el peor de los casos, y O(N) en el mejor de los casos. (Estoy patinando sobre algunos detalles de implementación Java ... como combinar iteración e inserción de listas sin una gran penalización de complejidad ... pero creo que se puede hacer en este caso)

El algoritmo descuida la patología que mencioné en el primer párrafo y otras patologías; p.ej. que un elemento de B podría ser "igual a" múltiples elementos de A, o viceversa. Para hacer frente a esto, el algoritmo necesita comprobar cada b contra todos los elementos de la lista fusionada que no son instancias de B. Eso hace que el algoritmo O(N**2) en el mejor de los casos.

Answer 5

Si los elementos son hashable, esto se puede hacer en tiempo O (N), donde N es el número total de elementos en A y B.

def merge(A, B): 
    # Walk A and build a hash table mapping its values to indices. 
    amap = {} 
    for i, a in enumerate(A): 
     amap[a] = i 

    # Now walk B building C. 
    C = [] 
    ai = 0 
    bi = 0 
    for i, b in enumerate(B): 
     if b in amap: 
      # b is in both lists. 
      new_ai = amap[b] 
      assert new_ai >= ai # check for consistent input 
      C += A[ai:new_ai] # add non-shared elements from A 
      C += B[bi:i]   # add non-shared elements from B 
      C.append(b)   # add the shared element b 
      ai = new_ai + 1 
      bi = i + 1 
    C += A[ai:] # add remaining non-shared elements from A 
    C += B[bi:] # from B 
    return C 

A = [1, 2, 'c', 4, 5, 'f', 7] 
B = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
print merge(A, B) 

(Esto es sólo una implementación del algoritmo de Anon. Tenga en cuenta que puede verificar listas de entrada inconsistentes sin perjudicar el rendimiento y que el acceso aleatorio a las listas es no necesario.)