Generate all possible sequential strings from list using Python 3

Question

I have a list:

["toaster", "oven", "door"]

I need to get ALL the possible sequential words that can be created. The output should look like this:

["toaster", "toaster oven", "toaster oven door", "oven", "oven door", "door"]

What is the most efficient way to get this list? I've looked at itertools.combinations() and a few other suggestions found on Stack Overflow, but nothing that would produce this exact result.

For example, the above list is not a powerset, because only words adjacent to each other in the input list should be used. A powerset would combine toaster and door into toaster door, but those two words are not adjacent.

@AzatIbrakov thanks just corrected. "door" would be needed as well — django-d
– django-d, Commented May 21, 2018 at 12:00
@DeepSpace, I'm ONLY looking for strings in sequential order N+1 — django-d
– django-d, Commented May 21, 2018 at 12:02
"Sequential words" is not a thing. What you want are called substrings, which are subsequences made of all consecutive elements from the initial sequence. So you want to generate all substrings of that sequence. — Giacomo Alzetta
– Giacomo Alzetta, Commented May 21, 2018 at 12:10

Thierry Lathuille · Accepted Answer · 2018-05-21 12:42:27Z

10

You can do it like this:

words = ["toaster", "oven", "door"]  

length = len(words)
out = []
for start in range(length):
    for end in range (start+1, length+1):
        out.append(' '.join(words[start:end]))

print(out)

# ['toaster', 'toaster oven', 'toaster oven door', 'oven', 'oven door', 'door']

You just need to determine the first and last word to use.

You could also use a list comprehension:

[' '.join(words[start:end]) for start in range(length) for end in range(start+1, length+1)]

#['toaster', 'toaster oven', 'toaster oven door', 'oven', 'oven door', 'door']

edited May 21, 2018 at 12:42

answered May 21, 2018 at 12:06

Thierry Lathuille

24.4k10 gold badges49 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Giacomo Alzetta Over a year ago

Note: you can use for start in range(L-1) with L = len(words) because: 1) using lowercase l is evil and 2) the OP does not want the empty string and you are doing an unneccessary iteration anyway.

Martijn Pieters Over a year ago

Not sure why you range start all the way through to length + 1, you can safely remove the +1 there. It's not a problem because range(3, 3) is empty, but you make Python do that extra step without reason.

Martijn Pieters Over a year ago

@GiacomoAlzetta: no, not L-1, then start ends at 1, so you'd never get door on its own.

Martijn Pieters Over a year ago

@GiacomoAlzetta: and no to using L either. Just use length.

Martijn Pieters · Accepted Answer · 2018-05-21 12:13:31Z

3

You want to create sliding windows of increasing length, use the window() function from the top answer there inside a range() loop to increment the lengths:

from itertools import islice, chain

# window definition from https://stackoverflow.com/a/6822773

def increasing_slices(seq):
    seq = list(seq)
    return chain.from_iterable(window(seq, n=i) for i in range(1, len(seq) + 1))

for combo in increasing_slices(["toaster", "oven", "door"]):
    print(' '.join(combo))

This outputs:

toaster
oven
door
toaster oven
oven door
toaster oven door

edited May 21, 2018 at 12:13

answered May 21, 2018 at 12:04

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Comments

Michal · Accepted Answer · 2018-05-21 12:42:33Z

0

import itertools

a = ['toaster', 'over', 'door']

result = []
for i in [itertools.combinations(a, x + 1) for x in range(len(a))]:
    result += [' '.join(e) for e in list(i)]

print(result)

What do you think about this solution? The result is:

['toaster', 'over', 'door', 'toaster over', 'toaster door', 'over door', 'toaster over door']

answered May 21, 2018 at 12:42

Michal

1

1 Comment

101 Over a year ago

That includes non-sequential combos.

Collectives™ on Stack Overflow

Generate all possible sequential strings from list using Python 3

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related