生成所有连续子数组的算法

Question

使用以下输入，

[1, 2, 3, 4]

我正在尝试获得以下输出

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

目前我已经做了这样的算法，但是时间复杂度不好。

def find(height):
    num1 = 0
    out = []
    for i in range(len(height)):
        num2 = 1
        for j in range(len(height)):
            temp = []
            for x in range(num1, num2):
                temp.append(height[x])
            num2 += 1
            if temp: out.append(temp)
        num1 += 1
    return out

有什么办法可以加速该算法吗？

Answer 1

连续子序列

OP 在评论中指出他们对连续的子序列感兴趣。

选择连续子序列所需的只是选择起始索引i和结束索引j。然后我们可以简单地返回切片l[i:j]。

def contiguous_subsequences(l):
  return [l[i:j] for i in range(0, len(l)) for j in range(i+1, len(l)+1)]

print(contiguous_subsequences([1,2,3,4]))
# [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]

这个函数已经在 more_itertools 包中实现，它被称为substrings：

import more_itertools
print(list(more_itertools.substrings([0, 1, 2])))
# [(0,), (1,), (2,), (0, 1), (1, 2), (0, 1, 2)]

不连续的子序列

为了完整性。

查找可迭代对象的“幂集”是itertool 的秘诀：

import itertools
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

它也在包more_itertools中：

import more_itertools
print(list(more_itertools.powerset([1,2,3,4])))
# [(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]