Как получить все вложенные массивы массива длиной 2 или более эффективным способом?

Question

array =[1,2,3,4]

Результирующий подмассив должен быть ...

[1,2],[2,3],[3,4],[1,2,3],[2,3,4],[1,2,3,4]

Answer 1

Вы не можете получить свой результат в O(N).
Так как существует 2^N - 1 - N вложенных массивов с размером> 1, следовательно, общая сложность будет O(2^N), так как вы должны получить все вложенныемассивы.
Для решения O(2^N) вы можете найти общеизвестную проблему получения power set of a set.

Answer 2

Вы всегда можете попробовать это решение itertools.combinations(), чтобы получить все сомнительные подмассивы длины 2 или больше:

>>> from itertools import combinations
>>> array = [1, 2, 3, 4]
>>> [array[start:end+1] for start, end in combinations(range(len(array)), 2)]
[[1, 2], [1, 2, 3], [1, 2, 3, 4], [2, 3], [2, 3, 4], [3, 4]]

Answer 3

O (п)?Возможно, если у вас была бесконечная память со всеми возможными подмассивами в реальной / мнимой системе счисления, сохраненными для эффективного доступа, тогда, конечно, вы можете иметь любой алгоритм сложности, который вам нравится.

... Но, на самом деле, вы смотрите на что-то по линии O (n ^ 3), независимо от того, насколько эффективно вы это делаете.

>>> [lst[i:j + 1] for i in range(len(lst)) for j in range(i + 1, len(lst))]
[[1, 2], [1, 2, 3], [1, 2, 3, 4], [2, 3], [2, 3, 4], [3, 4]]

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