Unique combinations from list with "distance limit"

Question

Given the list a = ['a', 'b', 'c', 'd', 'e'], I would use itertools.combinations to get all unique combos like ['ab', 'ac', ...], as per the classic SO answer

How can I limit the unique combinations to items that are not farther away than n spots?

Example

If I want list items no more than n=2 spots away, I would accept 'ab' and 'ac' as combinations but not 'ae', because the distance between 'a' and 'e' is greater than n=2

Edit - code

Below the plain python code solution, which I'd avoid due to the double-for loop, that is not ideal for large lists

a = ['a', 'b', 'c', 'd', 'e']
n_items = len(a)
n_max_look_forward = 2

unique_combos = []
for i, item in enumerate(a):
    for j in range(i+1, min(i+n_max_look_forward+1, n_items)):
        unique_combos.append( item+a[j] )

print(unique_combos)

Answer 1

Complexity-wise, your solution is close to the best possible. You could refactor it to be a generator to generate the values only when you need them so that you don't have to hold all of them in memory at the same time:

def combis(source, max_distance=2):
    for i, item in enumerate(source):
        for j in range(i+1, min(i+max_distance+1, len(source))):
            yield item+source[j]

You can then iterate over the generator:

>>> for combi in combis(['a', 'b', 'c', 'd', 'e']):
...     print(combi)
...
ab
ac
bc
bd
cd
ce
de

If you need all of them in memory as a list, you can still use the generator to initialise it:

>>> list(combis(['a', 'b', 'c', 'd', 'e']))
['ab', 'ac', 'bc', 'bd', 'cd', 'ce', 'de']