Encontrar el número de secuencias posibles en una matriz, con condiciones adicionales

Question

Hay una secuencia {a1, a2, a3, a4, ..... aN}. Una carrera es la parte continua de la secuencia que aumenta estrictamente o disminuye estrictamente. P.ej. Si tenemos una secuencia {1,2,3,4,7,6,5,2,3,4,1,2} Tenemos 5 carreras posibles {1,2,3,4,7}, {7, 6,5,2}, {2,3,4}, {4,1} y {1,2}.

Dados cuatro números N, M, K, L. Cuente el número de secuencias posibles de N números que tiene exactamente M carreras, cada uno de los números en la secuencia es menor o igual a K y la diferencia entre los números adyacentes es menos que igual a L

La pregunta fue formulada durante una entrevista.

Solo pude pensar en una solución de fuerza bruta. ¿Cuál es una solución eficiente para este problema?

Answer 1

Supongo que quiere decir con 'solución de fuerza bruta' lo que podría querer decir con 'solución directa que implica bucles anidados sobre N, M, K, L'? A veces, la solución directa es lo suficientemente buena. Una de las veces en que la solución directa es lo suficientemente buena es cuando no tienes una mejor solución. Otra de las veces es cuando los números no son muy grandes.

Con eso fuera de mi pecho escribiría los bucles en la dirección opuesta, o algo así. Es decir:

1. crear 2 estructuras de datos auxiliares, uno para contener los índices de los números < = K, uno para los índices de los números cuya diferencia con sus vecinos es < = L.
2. Ejecute la lista de números y llene las estructuras de datos auxiliares anteriores.
3. Encuentra la intersección de los valores en esas 2 estructuras de datos; estos serán los índices de lugares interesantes para comenzar a buscar carreras.
4. Mire en cada uno de los lugares interesantes.

Hasta que alguien demuestre lo contrario, esta es la solución más eficiente.

Answer 2

Utilice la programación dinámica. Para cada número en la subcadena mantenga un recuento separado de subsecuencias maximal creciente y máximamente decreciente. Cuando agrega incrementalmente un número nuevo al final, puede usar estos conteos para actualizar los recuentos del nuevo número. Complejidad: O (n^2)

Answer 3

Esto se puede reformular como un problema de recurrencia. Mire su problema como encontrar # (N, M) (suponga que K y L son fijos, se usan en las condiciones de recurrencia, por lo que se propagan en consecuencia). Ahora comience con las funciones de conteo más restringidas A (N, M; a) y D (N, M, a), donde A cuenta los conjuntos con la última ejecución ascendente, D los cuenta con la última ejecución descendiendo, y a es el valor de el último elemento en el conjunto.

Exprese el número (N, M) en términos de A (N, M; a) y D (N, M; a) (es la suma sobre todo a). Puede notar que hay relaciones entre los dos (como el reflejo A (N, M; a) = D (N, M; K-a)) pero eso no importará mucho para el cálculo, excepto para acelerar el llenado de la mesa.

Ahora A (N, M; a) se puede expresar en términos de A (N-1, M; w), A (N-1, M-1; x), D (N-1, M ; y) y D (N-1, M-1; z). La idea es que si comienzas con un conjunto de tamaño N-1 y conoces la dirección de la última ejecución y el valor del último elemento, sabrás si añadir el elemento a se agregará a una ejecución existente o agregará una ejecución. Entonces puedes contar la cantidad de formas posibles de obtener lo que quieres de las posibilidades del caso anterior.

Te dejaré escribir esta recursividad abajo. Tenga en cuenta que aquí es donde representa L (solo sume los que obedecen la restricción de distancia L) y K (busque casos extremos).

Termine la recursión usando el hecho de que A (1, 1; a) = 1, A (1, x> 1; a) = 0 (y de manera similar para D).

Ahora, como se trata de una recursión múltiple, asegúrese de que su implementación almacene los resultados en una tabla y comience por la búsqueda (comúnmente llamada programación dinámica).