Python：从一个列表中获取所有不重叠的、连续的子列表

Question

我正在尝试找出一个 elegant/efficient 解决方案来在列表中查找子列表，但有一定的限制。

例如，给定此列表：

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

Python：从一个列表中获取所有不重叠的、连续的子列表

Python: Get all the non-overlapping, consecutive sublists from a list

python

iteration

list

sublist