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

Question

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

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

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)

Answer 1

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

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']]]