Python: получить все непересекающиеся последовательные списки из списка - PullRequest
Новая
       29

Python: получить все непересекающиеся последовательные списки из списка

0 голосов
/ 29 ноября 2018

Я пытаюсь найти элегантное / эффективное решение для поиска подсписков в списке с определенными ограничениями.

Например, с учетом этого списка: 

values = ['a', 'b', 'c', 'd', 'e', 'f']

Изначение для maxLength: 

maxLength = 4

Найти все подсписки в списке значений так, чтобы:

  • Длина подсписка была от 1 до maxLength
  • Подсписки последовательны
  • Подсписки не перекрываются

Итак, в этом примере это приемлемые решения: 

[['a'], ['b'], ['c'], ['d'], ['e'], ['f']]
[['a', 'b'], ['c'], ['d'], ['e'], ['f']]
...
[['a', 'b'], ['c', 'd', 'e'], ['f']]
...
[['a', 'b', 'c', 'd'], ['e', 'f']]
...
[['a', 'b'], ['c', 'd', 'e', 'f']]

Это недопустимо: 

[['a', 'b'], ['d', 'e'], ['f']]           #Error: not consecutive, 'c' is missing
[['a', 'b', 'c'], ['c', 'd', 'e'], ['f']] #Error: overlapping, 'c' is in two subsets
[['a', 'b', 'c', 'd', 'e'], ['f']]        #Error: the first sublist has length > maxLength (4)

1 Ответ

0 голосов
/ 29 ноября 2018

Вы можете использовать рекурсию: 

values = ['a', 'b', 'c', 'd', 'e', 'f']
maxLength = 4

def groupings(d):
  if not d:
    yield []
  else:
    for i in range(1, maxLength+1):
      for c in groupings(d[i:]):
         yield [d[:i], *c]

_d = list(groupings(values))
new_d = [a for i, a in enumerate(_d) if a not in _d[:i]]

Вывод: 

[[['a'], ['b'], ['c'], ['d'], ['e'], ['f']], [['a'], ['b'], ['c'], ['d'], ['e', 'f']], [['a'], ['b'], ['c'], ['d', 'e'], ['f']], [['a'], ['b'], ['c'], ['d', 'e', 'f']], [['a'], ['b'], ['c', 'd'], ['e'], ['f']], [['a'], ['b'], ['c', 'd'], ['e', 'f']], [['a'], ['b'], ['c', 'd', 'e'], ['f']], [['a'], ['b'], ['c', 'd', 'e', 'f']], [['a'], ['b', 'c'], ['d'], ['e'], ['f']], [['a'], ['b', 'c'], ['d'], ['e', 'f']], [['a'], ['b', 'c'], ['d', 'e'], ['f']], [['a'], ['b', 'c'], ['d', 'e', 'f']], [['a'], ['b', 'c', 'd'], ['e'], ['f']], [['a'], ['b', 'c', 'd'], ['e', 'f']], [['a'], ['b', 'c', 'd', 'e'], ['f']], [['a', 'b'], ['c'], ['d'], ['e'], ['f']], [['a', 'b'], ['c'], ['d'], ['e', 'f']], [['a', 'b'], ['c'], ['d', 'e'], ['f']], [['a', 'b'], ['c'], ['d', 'e', 'f']], [['a', 'b'], ['c', 'd'], ['e'], ['f']], [['a', 'b'], ['c', 'd'], ['e', 'f']], [['a', 'b'], ['c', 'd', 'e'], ['f']], [['a', 'b'], ['c', 'd', 'e', 'f']], [['a', 'b', 'c'], ['d'], ['e'], ['f']], [['a', 'b', 'c'], ['d'], ['e', 'f']], [['a', 'b', 'c'], ['d', 'e'], ['f']], [['a', 'b', 'c'], ['d', 'e', 'f']], [['a', 'b', 'c', 'd'], ['e'], ['f']], [['a', 'b', 'c', 'd'], ['e', 'f']]]
...