Algorithm that generates all contiguous subarrays

Question

Using the following input,

[1, 2, 3, 4]

I'm trying to get the following output

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

As far I have made such an algorithm, but time complexity is not good.

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

Is there any way to speed up that algorithm?

Answer 1

Contiguous sub-sequences

The OP specified in comments that they were interested in contiguous sub-sequences.

All that is needed to select a contiguous sub-sequence is to select a starting index i and an ending index j. Then we can simply return the slice 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]]

This function is already implemented in package more_itertools, where it is called substrings:

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

Non-contiguous sub-sequences

For completeness.

Finding the "powerset" of an iterable is an itertool recipe:

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))

It is also in package 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)]