Prueba si existe un entero k para agregar a una secuencia para que sea una subsecuencia de otra secuencia

Question

Supongamos que la secuencia $ a $ contiene $ n $ enteros $ A_1, A_2, A_3, \ LDOTS, A_N $ y secuencia $ b $ contiene $ m $ enteros $ b_1, b_2, b_3, \ ldots, b_m $ . Sabemos que $ m \ geq n $ . Asumimos sin pérdida de generalidad que ambas secuencias $ A $ y $ b $ se clasifican en orden ascendente.

¿Cuál es el algoritmo más rápido para determinar si existe un entero $ k $ de tal que la secuencia $ A_1 + k, A_2 + K, A_3 + K, \ LDOTS, A_N + K $ es una subsecuencia de la secuencia $ b $ ?

Aquí hay un algoritmo ingenuo, que tomaría $ o (n (m-n)) $ tiempo. Almacene la secuencia $ b $ como Hashtable. Para cada elemento $ b_j $ de la $ b $ (excepto la más grande $ n $ elementos), use $ b_j-a_1 $ como su conjetura en $ k $ ; Puede verificar esta suposición comprobando si cada uno de $ a_1 + k, \ dots, a_n + k $ está en el hashtable $ B $ . Esto lleva $ o (n) $ tiempo esperado por adivinación en $ k $ , y usted hace $ mn $ Adivina, por lo que en total, el tiempo de ejecución esperado es $ o (n (mn)) $ . ¿Podemos hacerlo mejor?

Me encontré con este problema mientras intentaste coincidir con dos imágenes binarias (prueba si una imagen contiene la otra).

Answer 1

Aquí hay una heurística que no siempre funcionará, pero debe funcionar con una alta probabilidad si los enteros en las matrices se eligen al azar desde un espacio lo suficientemente grande.

Inicializar un hashtable de conteos $ C $ a todos los ceros. Luego, repita $ t $ tiempos: selección al azar $ i, j $ , cómputo $ b_j-a_i $ , e incrementar $ c [b_j-a_i] $ . Finalmente, clasifique $ C $ por los conteos, desde el mayor recuento hasta el más pequeño; luego, para cada uno de los valores más grandes de $ c [k '] $ , intente $ k' $ Como su conjetura en $ k $ y verifique cada conjetura.

Observe que en cada iteración, la probabilidad de incrementar $ c [k] $ es al menos $ 1 / m $ ; Considerando que si $ l \ ne k $ , esperamos $ c [l] $ para ser incrementado mucho más Rara vez (asumir los enteros en las matrices son lo suficientemente aleatorios y lo suficientemente grandes). Por lo tanto, después de $ t $ iteraciones, esperamos $ \ mathbb {e} [c [k]] \ ge t / m $ pero $ \ mathbb {e} [c [l]] \ ll t / m $ . Así, una vez $ t $ es lo suficientemente grande, $ c [k] $ debe ser más grande que cualquier otro Entrada en $ C $ .

¿Qué tan grande hace $ t $ necesito ser? Espero que $ t= o (m \ log m) $ debe ser suficiente, en función de una aproximación de teorema de límite central para los conteos $ C [l] $ , suponiendo que estamos dispuestos a aceptar una pequeña probabilidad de error (que se puede impulsar exponencialmente pequeño). El factor constante oculto por la notación de BIG-O podría ser no trivial.

Esto es solo un heurístico, y ciertamente habrá entradas donde falla.

Answer 2

Aquí hay un algoritmo que se ejecuta en $ \ mathcal {o} (n \ sqrt {n} + m \ log m) $ tiempo.

Permitir $ w $ denota la función que para entero $ t $ , cuenta el número de pares que su diferencia es $ t $ : $ w (t)=lvert \ {(x, y): x \ en A, Y \ IN B, YX= T \} \ Rvert $ . Si tuviéramos acceso a $ W (t) $ podríamos simplemente encontrar su máximo y ver si es $ n $ o no. La idea principal es estimar $ w $ usando la transformación rápida de Fourier. Si los números están delimitados, producirá la solución exacta, de lo contrario, se puede usar el módulo a un número suficientemente grande y luego verificar las soluciones una vez que se encuentren.

Let $ N, M $ ser enteros (a definirse más adelante), y $ u, v \ in \ mathbb {r} ^ n $ ser vectores definidos como $$ u [i]=lvert \ {x \ en un \ colon m-x \ equiv i \ pmod n \} \ rvert $$ $$ v [i]=lvert \ \ \ \ \ \ \ \ \ colon m + y \ equiv i \ pmod n \} \ rvert $$ Deje que $ w= u * v $ denota la convolución circular de estos dos vectores. Entonces si hay $ k $ tal que $$ \ forall x \ en A \ existe y \ in b: y-x= k, $$ Entonces podemos concluir $$ w [k \ bmod n]=sum_ {i: v [i] \ neq 0} v [i] u [ik \ bmod n]= n $$ que por construcción es el valor máximo que $ W $ puede alcanzar. Por lo tanto, solo necesitamos verificar si $ \ max_i w (i)= n $ o no. Luego, verificamos la corrección de la solución marcando los elementos originales. Computación $ w $ se puede hacer por FFT e inverso FFT en $ \ mathcal {o} (n \ log n) $ tiempo, y luego encontrar el elemento máximo y verificarlo se necesita $ n $ pasos, por lo que en general $ \ mathcal {O} (n \ log n) $ tiempo y espacio.

Si los números en ambos conjuntos están limitados por $ n $ Esta es una solución exacta. Pero si elige $ n $ demasiado pequeño, $ w (i)= n $ puede suceder debido a colisiones. Para que podamos verificar todos los elementos para todos los índices que $ w (i) \ ge n $ ; Puede haber varios de ellos, pero su número puede estar limitado. Tener $ \ ell $ los índices, uno debe tener al menos $ 1 + 2 + \ dots + \ ell $ colisiones, lo que implica $$ P [\ lvert \ {i \ colon w [i] \ ge n \ \ rvert \ ge \ ell] \ le p [\ texto {# colisiones} \ ge ( \ ELL + 1) \ ELL / 2]. $$ Hay $ nm $ emparejamientos de elementos de $ a $ y $ B $ . Si recogemos un número primo $ n $ de tal manera que $ n> 2m $ y elija $ M $ uniformemente al azar de $ \ {1, \ puntos, n \} $ , la probabilidad de colisión está limitada por $ 1/2M $ , por lo que por la desigualdad de Markov es $$ \ le \ frac {nm / n} {\ ell ^ 2/2} \ le \ frac {n} {\ ell ^ 2} $$ Así que con probabilidad tan cerca de $ 1 $ como desee, $ \ ell=mathcal {o} (\ sqrt {n }) $ . Por lo tanto, la complejidad del tiempo general del algoritmo es $$ \ mathcal {o} (n \ sqrt {n} + m \ log m) $$ en el que $ m \ log m $ es el paso FFT y IFFT (ya que establecemos $ n= 2m $ ), y $ n \ sqrt {n} $ es el paso de verificación.

Hay dos formas en que veo para mejorar esto:

1. uno puede ejecutar $ \ log n $ instancias separadas del algoritmo sin la verificación, y tomar la intersección de índices máximos que $ w [i] \ ge n $ (después de cambiar por $ m $ ). Si uno puede demostrar que la cantidad de colisiones compartidas se reduce por $ 1/2 $ o alguna otra constante cada vez, esto mostraría un tiempo total de funcionamiento de $ \ mathcal {o} (M \ log ^ 2 m) $ .
2. uno puede construir un mejor mecanismo de hashing para $ u $ y $ v $ y use Momentos más altos para Markov y hacer que la concentración sea más nítida.

Sin embargo, si está buscando una solución práctica, este algoritmo podría funcionar bien. Por ejemplo, los wors

Comportamiento en T $ \ ell \ aprox \ sqrt {n} $ solo ocurre cuando los conjuntos son progresiones casi aritméticas.Si elige elementos casi al azar, la garantía será mucho más fuerte.Además, puede detener el paso de verificación tan pronto como encuentre un error.

Answer 3

Este es un algoritmo completamente diferente, que creo que funciona en $ o (m \ log m) $ peor caso, y debe funcionar para números enteros o reales.

Supongamos que $ a $ y $ b $ ya están en orden ascendente, de lo contrario gastar $ o (n \ log n + m \ log m) $ para ordenarlos. Fortalecemos ligeramente el requisito de algoritmo $ \ mathcal {a} (a, b) $ para devolver todos los índices $ i $ $ de tal que $ a $ se puede asignar a $ b $ con offset $ k= b_i-a_1 $ , lo que significa que el mapeo comienza en $ b_i $ en adelante. La idea de alto nivel es resolver los sub-problemas correspondientes a un Subarrio de $ a $ y fusiona los índices de una manera que solo permanezcan soluciones válidas.

La recursión, sin embargo, depende de qué tan cerca $ A $ es a una progresión aritmética. Formalmente, deja que la periodicidad $ \ tau (A) $ se definí como: $$ \ tau (A)=min \ {s \ in \ mathbb {n} ^ +: a_ {i + s + 1} -a_ {i + s}= a_ {I + 1} - A_I \ Text {para todo VALIDO} i, s \} $$ En palabras, esto significa elementos de $ a $ , son periódicos con un ciclo mínimo $ \ tau (a) $ , hasta alguna offset.

caso i ( $ \ tau (a) let $ s=tau (a) $ y $ \ ell= a_s - a_1 $ . Compute recursivamente $ i=mathcal {a} (a [1: s], b) $ . Una observación es que si $ i, j \ in i $ , correspondiente a los conjuntos de índice $ j_i, j_j $ , y $ b_j - b_i=ell $ , los conjuntos de índice $ j_i, j_j $ puede ser Concatenado para mostrar $ i \ in \ mathcal {a} (a [1: 2s], b) $ . Esta es una consecuencia simple de $ a $ siendo $ s $ periódica, y $ b_j= b_i + \ ell $ asegura que el conjunto de índice $ j_j $ comienza donde $ J_i $ finaliza. Dejar $$ r [i]=lvert \ {j \ in i \ colon J> i, b_j - b_i \ texto {divisible by} \ ell \} \ rvert $$ Luego, $ r [i] $ se puede calcular en función de $ r [i '] $ que < span class="Math-contenedor"> $ i '> i $ , y el nuevo conjunto de índice $ i' $ , son los índices que $ r [i] \ ge n / s $ . El costo de este paso está delimitado por $ o (m) $ .

caso II ( $ \ tau (a)> n / 3 $ ) : Por definición, para $ s= n / 3 $ Debe haber un índice $ i $ que $ A_ {i + 1} -a_i \ neq a_ {i + 1 + s} -a_ {i + s} $ . Si $ i \ le n / 3 $ , tendremos $ i, i + s \ le 2n / 3 $ < / span> que certifica que $ \ tau (A [1: 2N / 3])> N / 3 $ . De lo contrario, $ i> n / 3 $ implica que $ \ tau (a [n / 3: n])> n / 3 $ .

wlog asume $ \ tau (A [1: 2N / 3)> N / 3 $ y elija la mitad inferior $ A '= a [1: n / 2] $ Para recurtar (de lo contrario, elegir la mitad superior, los mismos argumentos seguirían). Compute recursivamente $ i=mathcal {a} (a ', b) $ . Para cada índice $ i \ in i $ , verifique si el resto de la secuencia se puede encontrar en $ b $ . Dado que ambas secuencias se ordenan, esto se puede hacer en $ o (n) $ Paso para cada índice, lo que implica un $ O (| i | \ cdot n) $ tiempo para calcular los índices válidos y devolverlos como $ \ mathcal {a} (a, b) $ . La eficiencia de este paso se basa en la siguiente reclamación:

Reclamación: $ | i | \ le 6m / n $ , lo que significa que las soluciones no son demasiado superpuestas.

Prueba de reclamación: Nos mostramos $ | i |> 6m / n $ conduce a una contradicción. Cada índice $ i \ in i $ es el punto de partida de un conjunto de índices $ j_i={i= j_1, \ DOTS, J_ {N / 2} \} \ subespeteq B $ , ese mapa $ a '$ a $ B $ hasta algunos compensados. Columna

Configuradamente, hay al menos $ 3M $ Índices: $$ \ sum_ {i \ in i} | j_i |= | I | N / 2 \ GE 6M / N \ CDOT N / 2= 3M $$ Desde $ | b |= m $ , por principio de pigeonhole, hay al menos un índice $ x \ en b $ < / span> aparece en 3 soluciones separadas: $$ \ existe x \ en b, r, s, p \ in i \ colon \; x \ en j_r \ tap j_s \ cap j_p $$

Permitir $ s $ ser la mediana de los tres $ r . Desde $ x \ en j_s $ , y $ | j_s |= n / 2 $ , $ x $ particiones $ j_s $ a dos partes, una de las cuales debe tener menos de $ n / 4 $ Índices, que asumimos que es la parte inferior: $$ J_S={J_1= S, J_2, \ DOTS, J_ \ ELL= X \}, \ ELL \ Le N / 4 $$ Por construcción, $ s= j_1 $ se asigna a $ a_1 $ , hasta $ A_ \ ELL $ hasta algunos compensados. Pero también tenemos $ x \ en j_p $ , esto implica un periodicto menos que $ \ ell \ le n / 4 $ en $ a '$ , que contradice $ \ tau (a')> n / 3 $ . (Hay algunos detalles que agregaré más tarde)

complejidad general En cada paso de la recursión, pagamos $ o (m) $ . La periodicidad $ \ tau (a) $ también se puede calcular en $ o (n) $ , por Computación del sufijo más largo que también es prefijo, de $ \ mathrm {dif} (a) $ , es decir, la matriz de incremento $ A_2-A_1, \ DOTS, A_N-A_ {N-1} $ . Sin embargo, el tamaño del problema se reduce al menos $ 1/2 $ en cada paso recursivo. Habrá $ \ log n $ Pasos en el peor de los casos, lo que implica que la complejidad del tiempo está limitada por $ O (M \ log n) $ . Agregando los costos de clasificación, y desde $ m> n $ , la complejidad general está limitada por el tiempo de clasificación $ o (m \ log m) $