Inserción eficiente en la lista manteniendo el número de inversiones mínimo

Suponga dos listas de elementos comparables: u y s. Deje que INV (u) sea el número de inversiones en u.

Estoy buscando un algoritmo eficiente para insertar los elementos de s en u con un aumento mínimo de INV (u).

Básicamente, me gustaría insertar objetos en una lista mientras la mantengo "lo más ordenada posible" mientras mantengo el orden de la primera lista.

Ejemplo:

u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

Como puede ver, no existe una solución óptima única.

Me alegraría cualquier tipo de ideas o dirección a considerar.

Esta es una elaboración sobre la respuesta de trevore. Es demasiado largo para caber en un comentario y contiene las pruebas de su solución (o al menos cómo lo entiendo).

Puede mostrar que en cualquier solución óptima, los elementos de aparecerán ordenados. $s$Si no, suponga y aparecen en orden inverso en una solución óptima. Sea σ 1 el número de elementos entre s 1 y s 2 que son menores que s 1 y σ 2 y β 2 ≤ β 1 . Intercambio s $s_1 < s_2$$\sigma_1$$s_1$$s_2$$s_1$ es el número de elementos que son mayores que s 1 . Defina σ 2 y β 2 de manera similar para s 2 . Tenga en cuenta que σ 1$\beta_1$$s_1$$\sigma_2$$\beta_2$$s_2$$\sigma_1 \leq \sigma_2$$\beta_2 \leq \beta_1$$s_1$ y cambiará el número de inversiones por - β 1 + β 2 - σ 2 + σ 1 - 1, que es a lo sumo -1.$s_2$$-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$

No es difícil ver que los elementos de se pueden insertar de forma independiente. $s$Como aparecen ordenados, los elementos de no "sienten" la presencia del otro. Es decir, los pares de elementos de s no contribuyen al recuento de inversión. Para hacer eso, inserte la mediana de s óptimamente en tiempo lineal. Luego, recursivamente, inserte elementos de s menos que la mediana a la izquierda de la mediana y elementos más grandes que la mediana a su derecha.$s$$s$$s$$s$

Deje que la mediana se inserte en la posición , el tiempo de ejecución de esta satisface, T ( | s | , | u | ) = T ( | s | / 2 , | u | - k ) + T ( | s | / 2 , k ) + | u | + | s | , el lineal | s $k$$T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$$|s|$factor es para encontrar la mediana y barajar los elementos de . Es fácil mostrar por inducción que T ( | s | , | u | ) = O ( | s | log | s | + | u | log | s | ) .$s$$T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$

Tenga en cuenta que la dependencia de Aquí es óptimo. Dado que resolver el problema con u vacío es equivalente a ordenar s usando solo comparaciones. La dependencia de | u | También es óptima, ya que el problema para una lista unitaria s y una lista u debe requerir un trabajo lineal.$|s|$$u$$s$$|u|$$s$$u$

Ok, aquí está mi solución:

Una observación (que más o menos probé) es que una solución óptima siempre será aquella en la que s se ordena de forma ascendente. Esto da lugar a un algoritmo O ((| u | + | s |) * log (| s |)).

Para encontrar la solución óptima para un solo elemento, haga lo que dije en mi comentario: tome un elemento de s, compárelo con cada elemento en u de izquierda a derecha, incremente un contador es una inversión y transfiera el número previamente calculado. Luego recorra la lista de derecha a izquierda con el mismo elemento, aumentando los recuentos para cada posición.

Esto es O (| u |).

Ordena.

Para el elemento medio de s en la posición m: Encuentre la mejor posición b en u (usando el método de arriba).

Divida s en m y u en b y llame recursivamente con las partes izquierda y derecha, concatenando los resultados con m en el orden correcto.

Deténgase tan pronto como esté vacío.