Is there a more efficient algorithm to produce sub list combination?

Question

For example, for the list 'letters', I want to produce 'symbols' as below:

['ab', 'abc', 'abcd', 'bc', 'bcd', 'cd']

Now I current code is below:

letters = ['a', 'b', 'c', 'd']
letter_len = len(letters)
symbols = []
for i in range(letter_len):
    for j in range(i+1, letter_len):
        sub = letters[i:j + 1]
        sub = ''.join(sub)
        symbols.append( sub)

print(symbols)

Check the `itertools` documentation to see if it has any functions or recipes that do this. If not, your code looks pretty good. — Barmar, Jul 26 '22 at 21:07
seconding `itertools`; you might consider iterating first over the collection of the desired lengths `(2,3,4)`, calling `.combinations()` for each, though this will produce non-adjacent substrings (for example `"bd"`, which you may find you actually want, but is excluded from your example) and also a different ordering (all the length 2, all the length 3.. though this _can_ be `sorted()` away) https://docs.python.org/3/library/itertools.html#itertools.combinations — ti7, Jul 26 '22 at 21:18
"I want to produce 'symbols' as below:" What is the rule that tells you that these are the correct results? If I tell you, for example, that I think the result should also include `'a'`, or `'ad'`, or `'ba'`, why am I wrong? — Karl Knechtel, Jul 26 '22 at 21:22
I think `'a'` is a substring of `'abcd'`. I also don't understand why start with a list of individual letters if the results should be substrings of a string. — Karl Knechtel, Jul 26 '22 at 21:25

ti7 · Answer 1 · 2022-07-26T21:46:09.803

If you only want adjacent values, it's probably most efficient to slide a window across the input, slicing for the substrings you want, rather than splitting and joining them

As a bonus, the same logic will work for lists

def multi_adjacent(letters, min_gap=2):
    # further opportunity for dynamic maximum length and bounds-checking
    for idx_start in range(len(letters)-(min_gap-1)):
        for idx_end in range(idx_start+min_gap, len(letters)+1):
            yield letters[idx_start:idx_end]  # slice for substring

>>> list(multi_adjacent("abcd"))
['ab', 'abc', 'abcd', 'bc', 'bcd', 'cd']
>>> list(multi_adjacent("abcd", 3))
['abc', 'abcd', 'bcd']
>>> list(multi_adjacent([1,2,3,4]))
[[1, 2], [1, 2, 3], [1, 2, 3, 4], [2, 3], [2, 3, 4], [3, 4]]

If you're really after every grouping (not just adjacent ones), itertools.combinations can provide this

from itertools import combinations

def multi_combination(letters):
    for grouping_size in range(2, len(letters)+1):
        for grouping in combinations(letters, grouping_size):
            yield "".join(grouping)

>>> sorted(multi_combination("abcd"))
['ab', 'abc', 'abcd', 'abd', 'ac', 'acd', 'ad', 'bc', 'bcd', 'bd', 'cd']

Is there a more efficient algorithm to produce sub list combination?

1 Answers1