Detección de ciclo en una lista vinculada: Teoría exhaustiva

Question

Este NO es el problema sobre la detección de ciclo en una lista vinculada utilizando el método famous Hare and Tortoise.

En el método de la tortuga & Tortoise tenemos punteros funcionando en velocidades 1x y 2x para determinar que se encuentran y estoy convencido de que es la forma más eficiente y el orden de ese tipo de búsqueda es O (n).

El problema es que tengo que encontrar una prueba (prueba o desaprobación) de que es posible que dos punteros siempre se encuentren cuando la velocidad de movimiento es Ax (A veces x) y Bx (B veces x) y A no es igual a B. Donde A y B son dos enteros aleatorios que operan en una lista vinculada con un ciclo presente.

Esto fue preguntado en una de las entrevistas a las que asistí recientemente y no pude demostrar de manera exhaustiva a mí mismo que si lo anterior es posible. Cualquier ayuda apreciada.

Answer 1

Supongamos que hay un bucle, digamos de longitud L.

Fácil primer caso

Para hacerlo más fácil, en primer lugar considerar el caso en que las dos partículas toda bucle al mismo tiempo. Estas partículas están en la misma posición siempre que n*A = n*B (mod L) para algún entero positivo n, que es el número de pasos hasta que se encuentran de nuevo. Tomar n=L da una solución (aunque puede haber una solución más pequeña). Así que después de L unidades de tiempo, la partícula A ha realizado A viajes alrededor del circuito para volver al principio y la partícula B ha realizado B viajes alrededor del circuito para volver al principio, donde felizmente colisionan.

caso general

Ahora lo que sucede cuando no entran en el bucle al mismo tiempo? Deje A ser la partícula más lenta, es decir A<B, y suponga que A entra en el bucle en el tiempo m, y llamemos a la posición en la que A entra en el bucle 0 (dado que están en el bucle, nunca pueden abandonarlo, entonces Estoy simplemente cambiando el nombre de las posiciones restando A*m, la distancia A ha viajado después de m unidades de tiempo).Entonces, en ese momento, B ya está en la posición m*(B-A) (su posición real después de m unidades de tiempo es B*m y su posición cambiada es por lo tanto B*m-A*m). Entonces tenemos que mostrar que hay un tiempo n tal que n*A = n*B+m*(B-A) (mod L). Es decir, necesitamos una solución a la ecuación modular

(n+m) * (A-B) = 0 (mod L) 

Tomando n = k*L-m para k suficiente como para que k*L>m hace el truco grande, aunque, de nuevo, puede haber una solución más pequeña.

Por lo tanto, sí, siempre se encuentran.

Answer 2

Si sus dos tamaños de pasos tienen un factor común x: digamos que los tamaños de los pasos son Axe y Bx, solo considere la secuencia que obtiene de tomar la secuencia original y tomar cada elemento x'th. Esta nueva secuencia tiene un ciclo si y solo si la secuencia original lo hace, y tomar pasos de tamaño A y B equivale a tomar pasos de tamaño Ax y Bx en la secuencia original.

Esta reducción significa que es suficiente para demostrar que el algoritmo funciona cuando A y B son coprime.

Answer 3

La hipótesis es falsa. Por ejemplo, si ambos punteros realizan saltos de un tamaño par, el ciclo también es de tamaño par, y la distancia entre los punteros es impar, nunca se encontrarán.

UPD esto es aparentemente una situación imposible. Debido a que los dos indicadores comienzan en el mismo punto, la distancia entre ellos siempre será pareja.