skuteczny program do drukowania i/lub powracającego wszystkie coraz krótsze sekwencje o rozmiarze 3 w tablicy

Question

Biorąc pod uwagę macierz jak

1, 6, 5, 2, 3, 4

się do wydrukowania

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

Jaki jest najlepszy sposób na zrobienie tego? Czy to jest programowanie dynamiczne?

Czy jest lepszy sposób niż bruteforce O (n3)? Jestem pewien, że tak.

Dlatego mówię programowanie dynamiczne dlatego widzę to jako coś jak

• na „1” (wydrukować wszystkie wyniki sub problemu reszty tablicy z podciągów rozmiaru 2).

• na „2” (wydruk wszystkich wyników cząstkowych problemów reszty tablicy z subseqences wielkości 2)

i tak dalej.

Jednak w powyższych dwóch wynikach występuje wiele pokryć, więc musimy znaleźć skuteczny sposób na ponowne wykorzystanie tego, jak sądzę.

Cóż, to tylko przypadkowe myśli. Możesz poprawić mnie za pomocą odpowiedniego opowiadania.

OK, pozwól, że poprawię, jeśli nie wydrukuję, potrzebuję różnych zwracanych sekwencji rosnących. Chodzi mi o to, że muszę znaleźć sposób na uzyskanie tych sekwencji w najbardziej efektywny sposób.

Answer 1

Możesz przechodzić przez tablicę i pamiętać, jakie częściowe sekwencje są możliwe do bieżącego punktu. Druk i zapomnieć o sekwencje, które osiągają długość 3.

Przykład:

(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. 

wyzwaniem wydaje się leżeć w wyborze odpowiedniej struktury danych dla pamiętanych podciągów.

Answer 2

1. Utwórz listę uporządkowanych par (a, b) tak, że < b oraz Index (a) < Index (b). O (n^2)
2. Posortuj listę (na a lub b - nie ma znaczenia) w O (n^2log (n)). Można utworzyć O (nlog (n)) w zależności od struktury danych.
3. Dla każdego elementu na liście znaleźć wszystkie pasujące pary uporządkowane za pomocą przeszukiwanie binarne - najgorszy O (n^3log (n)), średniego przypadku O (n^2log (n))

Answer 3

W uogólniona przypadek trzeba obliczyć złożoności opiera się na dwóch rzeczach:

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

uogólniony sposób, że mogę myśleć, jest skonstruowanie analogiczny wykres na problem w czasie o (n^2):

Jeśli większa liczba ber przychodzi po mniejszej liczbie, Jest skierowana krawędź od mniejszej do niej.

Teraz, aby znaleźć wszystkie sekwencje długości d, należy rozpocząć od każdego numeru i wyprowadzić wszystkie ścieżki o długości (d - 1).

Jeśli zastosujesz metodę przechodzenia, taką jak BFS, złożoność będzie mniejsza niż O (d x (b^(d - 1))).

Można jednak użyć mnożenia sąsiednich macierzy, aby znaleźć ścieżki długości d, które spowodują zmniejszenie złożoności do wartości mniejszej niż O ((d - 2) x (b^3)). (N-ta moc macierzy sąsiedztwa powie Ci, ile ścieżek istnieje od każdego węzła do drugiego o długości N).

Istnieje algorithms, aby zmniejszyć nieco złożoność mnożenia macierzy kwadratowej.