Эффективная программа для печати / возврата всех возрастающих подпоследовательностей размера 3 в массиве

Question

Учитывая массив как

1, 6, 5, 2, 3, 4

нам нужно напечатать

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

Каков наилучший способ сделать это? Это динамическое программирование?

Есть ли лучший способ сделать это, чем грубая сила O (n3)? Я уверен, что есть.

Причина, по которой я говорю динамическое программирование, заключается в том, что я могу видеть это как что-то вроде

• для '1' (вывести все результаты подзадачи остальной части массива с подпоследовательностями размера 2).

• для '2' (вывести все результаты подзадач остальной части массива с последующими размерами 2)

и продолжай в том же духе.

Однако в двух приведенных выше результатах есть много совпадений, поэтому нам нужно найти эффективный способ повторного использования этого, я думаю.

Ну, это просто случайные мысли. Вы можете исправить меня с помощью правильной оценки.

ОК, позвольте мне исправить, если не печатать, мне нужно вернуть разные увеличивающиеся последовательности. Моя точка зрения заключается в том, что мне нужно найти подход, чтобы добраться до этих последовательностей наиболее эффективным способом.

Answer 1

В обобщенном случае вы должны рассчитать сложность на основе двух вещей:

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

Обобщенный метод, который я могу придумать, состоит в том, чтобы построить аналогичный граф для задачи в O (n ^ 2):

Если после меньшего числа появляется большее число, существует направленное ребро от меньшего к нему.

Теперь, чтобы найти все последовательности длины d, вам нужно начать с каждого числа и вывести все пути длины (d - 1).

Если вы используете метод обхода, такой как BFS, сложность будет меньше, чем O (d x (b ^ (d - 1))).

Однако вы можете использовать смежные матричные умножения, чтобы найти пути длины d, что снизит сложность до значения, меньшего O ((d - 2) x (b ^ 3)). (N-я степень матрицы смежности скажет вам, сколько путей существует от каждого узла к другому с длиной N).

Существуют алгоритмы , чтобы немного уменьшить сложность умножения квадратной матрицы.

Answer 2

Вы можете пройтись по массиву и запомнить, какие частичные последовательности возможны до текущей точки.Распечатайте и забудьте все последовательности, длина которых равна 3.

Пример:

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

Кажется, что проблема заключается в выборе подходящей структуры данных для запомненных подпоследовательностей.

Answer 3

1. Создайте список упорядоченных пар (a, b) так, чтобы a