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?

Itertools is a good tool for this. You can read about it here: https://docs.python.org/3/library/itertools.html Take a look at itertools.product in your case — sykezlol, Sep 30 '20 at 12:11
The three first answers list all sub-sequences, but your example output lists only contiguous sub-sequences. For instance, `[1,4]` is part of the output in all three answers, but is not part of your example output. Can you please clarify explicitly whether you are interested in **contiguous sub-sequences** or **all sub-sequences**? — Stef, Sep 30 '20 at 12:19
Does this answer your question? [How to get all possible combinations of a list’s elements?](https://stackoverflow.com/questions/464864/how-to-get-all-possible-combinations-of-a-list-s-elements) — deadshot, Sep 30 '20 at 12:24

Stef · Accepted Answer · 2020-09-30T12:43:19.707

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

Grayrigel · Answer 2 · 2020-09-30T17:50:40.400

You can simply do this using list comprehension in one line (O(N^2)), which is faster than your existing method:

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

Runtime comparison:

# your solution
>>> %timeit find(x)
9.23 µs ± 445 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

#itertools method suggested by 'stef' 
>>> %timeit list(more_itertools.substrings([1, 2, 3,4]))
3.18 µs ± 20.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

#List comprehension method
>>> %timeit [x[i:j] for i in range(len(x)) for j in range(i+1,len(x)+1)]
3.09 µs ± 27.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

John Titor · Answer 3 · 2020-09-30T12:30:01.257

1

How about:

a = [1, 2, 3, 4]
l = len(a)
ret = []
for i in range(l):
    ll = i + 1
    while ll <= l:
        ret.append(a[i:ll])
        ll +=1
print(ret)

prints:

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

edited Sep 30 '20 at 12:30

answered Sep 30 '20 at 12:14

John Titor

461
3
13

Program can not return `[1, 3]` as between 1 and 3 is 2. Same with the `[1, 4]` – Aleksander Ikleiw Sep 30 '20 at 12:17
clearly `[1,3]` and `[1,4]` are in the return value – John Titor Sep 30 '20 at 12:19
In the question, there is no such an output desired by me. – Aleksander Ikleiw Sep 30 '20 at 12:20

score 0 · Answer 4 · answered Sep 30 '20 at 16:06

Here, I've solved this using dynamic programming top - down approach.

The time complexity here is O(N^2).

I'm not sure if the time complexity for this problem could be reduce further ¯_(ツ)_/¯.

def find(arr):
    d = {}
    d[0] = []

    i = 1
    while (i <= len(arr)):
        d[i] = [] + d[i - 1]
        val = arr[i - 1]
        j = i - 1
        l = len(d[i - 1])
        while (j > 0):
            d[i].append(d[i - 1][l - j] + [val])
            j = j - 1

        d[i].append([val])
        i = i + 1

    return d[len(arr)]

input = [1, 2, 3, 4]
print(find(input))

Output:

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

Algorithm that generates all contiguous subarrays

4 Answers4

Contiguous sub-sequences

Non-contiguous sub-sequences

Linked