Уникальные комбинации из списка с «ограничением расстояния» - PullRequest
Новая
       37

Уникальные комбинации из списка с «ограничением расстояния»

0 голосов
/ 09 сентября 2018

Учитывая список a = ['a', 'b', 'c', 'd', 'e'], я бы использовал itertools.combinations, чтобы получить все уникальные комбинации, такие как ['ab', 'ac', ...], в соответствии с классическим SO ответом

Как я могу ограничить уникальные комбинации предметами, которые находятся не дальше, чем n пятна?

Пример

Если я хочу, чтобы элементы списка находились на расстоянии не более n=2, я бы принял 'ab' и 'ac' в качестве комбинаций, но не 'ae', поскольку расстояние между 'a' и 'e' больше n=2

Редактировать - код

Ниже простое решение на языке Python, которого я бы избегал из-за цикла double-for, которое не идеально подходит для больших списков 

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)

1 Ответ

0 голосов
/ 09 сентября 2018

По сложности ваше решение близко к наилучшему из возможных. Вы можете реорганизовать его в генератор, чтобы генерировать значения только тогда, когда они вам нужны, чтобы вам не приходилось одновременно хранить все их в памяти: 

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]

Затем вы можете перебрать генератор: 

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

Если вам нужны все из них в памяти в виде списка, вы все равно можете использовать генератор для его инициализации: 

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