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