programa eficiente para imprimir/retorno todos subsecuencias crecientes de tamaño 3 en una matriz

Question

Dado un vector como

1, 6, 5, 2, 3, 4

que necesita imprimir

1 2 3 
1 3 4 
1 2 4 
2 3 4 

¿Cuál es la mejor manera de hacer esto? ¿Es esta programación dinámica?

¿Hay una mejor manera de hacer que la bruteforce O (n3)? Estoy seguro de que hay

La razón por la que dicen programación dinámica es porque puedo ver esto como algo así como

• para '1' (imprimir todos los resultados de sub problema del resto de la matriz con subsecuencias de tamaño 2).

• de '2' (imprimir todos los resultados de los problemas sub del resto de la matriz con subseqences de tamaño 2)

y seguir así.

Sin embargo, hay una gran cantidad de superposición en los dos resultados anteriores, por lo que tenemos que encontrar una forma eficiente de reutilizar eso, supongo.

Bueno, estos son solo pensamientos aleatorios. Puedes corregirme con el appraoch correcto.

Bien, déjenme corregir, si no se imprime, necesito las diferentes secuencias de incremento devueltas. Mi punto es que necesito encontrar un enfoque para llegar a estas secuencias de la manera más eficiente.

Answer 1

Puede recorrer la matriz y recordar qué secuencias parciales son posibles hasta el punto actual. Imprimir y olvidar cualquier secuencia que alcanzan longitud 3.

Ejemplo:

(1 6 5 2 3 4) 
^
remember ((1)) 

(1 6 5 2 3 4) 
    ^
remember ((1) (1 6) (6)) 

(1 6 5 2 3 4) 
    ^
remember ((1) (1 6) (6) (1 5) (5)) 

(1 6 5 2 3 4) 
     ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2)) 

(1 6 5 2 3 4) 
     ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (1 2 3) (2 3) (3)) 
print and forget (1 2 3) 
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3)) 

(1 6 5 2 3 4) 
      ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3) (1 4) (1 2 4) (2 4) 
      (1 3 4) (2 3 4) (3 4) (4)) 
print and forget (1 2 4) 
print and forget (1 3 4) 
print and forget (2 3 4) 
done. 

El desafío parece residir en la elección de una estructura de datos apropiada para las subsecuencias recordados.

Answer 2

1. crear una lista de pares ordenados (a, b) de tal manera que un < b y el índice de (a) < Índice de (b). O (n^2)
2. Ordene esta lista (ya sea en a o b - no importa) en O (n^2log (n)). Se puede hacer O (nlog (n)) según la estructura de datos.
3. Para cada elemento de la lista, encontrar todos coincidencia de pares ordenados utilizando búsqueda binaria - peor caso O (n^3log (n)), caso O media (n^2log (n))

Answer 3

En el caso generalizado tienes que calcular la complejidad basado en dos cosas:

1- Count of input numbers (I will call it b) 
2- Length of output (I will call it d) 

un método generalizado de que se me ocurre, es la construcción de un gráfico análogo al problema en O (n^2):

Si un número más grande ber viene después de un número más pequeño. Hay un borde dirigido desde el más pequeño hacia él.

Ahora, para encontrar todas las secuencias de longitud d, debe comenzar desde cada número y dar salida a todas las rutas de longitud (d - 1).

Si usa un método transversal como BFS, la complejidad será menor que O (d x (b^(d - 1))).

Sin embargo, puede usar la multiplicación de matriz adyacente para encontrar las rutas de longitud d, lo que reducirá la complejidad a algo menor que O ((d - 2) x (b^3)). (La enésima potencia de una matriz de adyacencia te dirá cuántas rutas existen desde cada nodo a otro con una longitud de N).

Hay algorithms para reducir un poco la complejidad de la multiplicación de la matriz cuadrada.