使用所有组合将列表拆分为 n 个不均匀的桶

Question

我有一个这样的列表：

lst = [1,2,3,4,5,6,7,8,9,10]

并且我想在不更改列表顺序的情况下获得给定 n 个存储桶的所有拆分的组合。 n=3 的输出 exp:

[
 [1],[2],[3,4,5,6,7,8,9,10],
 [1],[2,3],[4,5,6,7,8,9,10],
 [1],[2,3,4],[5,6,7,8,9,10],
 .
 .
 .
 [1,2,3,4,5,6,7,8],[9],[10],
]

Python 是我使用的语言，但如果你能指导我使用一种算法，那也很好。我看到这个问题通常适用于字符串。但是在列表中无法弄清楚。

P.S。这是我的第一个问题。感谢任何关于如何改进问题的反馈。

Answer 1

尝试：

from itertools import product


def generate(n, l):
    for c in product(range(1, l), repeat=n - 1):
        s = sum(c)
        if s > l - 1:
            continue
        yield *c, l - s


lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 3

for groups in generate(n, len(lst)):
    l, out = lst, []
    for g in groups:
        out.append(l[:g])
        l = l[g:]
    print(out)

打印：

[[1], [2], [3, 4, 5, 6, 7, 8, 9, 10]]
[[1], [2, 3], [4, 5, 6, 7, 8, 9, 10]]
[[1], [2, 3, 4], [5, 6, 7, 8, 9, 10]]
[[1], [2, 3, 4, 5], [6, 7, 8, 9, 10]]
[[1], [2, 3, 4, 5, 6], [7, 8, 9, 10]]
[[1], [2, 3, 4, 5, 6, 7], [8, 9, 10]]
[[1], [2, 3, 4, 5, 6, 7, 8], [9, 10]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9], [10]]
[[1, 2], [3], [4, 5, 6, 7, 8, 9, 10]]
[[1, 2], [3, 4], [5, 6, 7, 8, 9, 10]]
[[1, 2], [3, 4, 5], [6, 7, 8, 9, 10]]
[[1, 2], [3, 4, 5, 6], [7, 8, 9, 10]]
[[1, 2], [3, 4, 5, 6, 7], [8, 9, 10]]
[[1, 2], [3, 4, 5, 6, 7, 8], [9, 10]]
[[1, 2], [3, 4, 5, 6, 7, 8, 9], [10]]
[[1, 2, 3], [4], [5, 6, 7, 8, 9, 10]]
[[1, 2, 3], [4, 5], [6, 7, 8, 9, 10]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9, 10]]
[[1, 2, 3], [4, 5, 6, 7], [8, 9, 10]]
[[1, 2, 3], [4, 5, 6, 7, 8], [9, 10]]
[[1, 2, 3], [4, 5, 6, 7, 8, 9], [10]]
[[1, 2, 3, 4], [5], [6, 7, 8, 9, 10]]
[[1, 2, 3, 4], [5, 6], [7, 8, 9, 10]]
[[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]]
[[1, 2, 3, 4], [5, 6, 7, 8, 9], [10]]
[[1, 2, 3, 4, 5], [6], [7, 8, 9, 10]]
[[1, 2, 3, 4, 5], [6, 7], [8, 9, 10]]
[[1, 2, 3, 4, 5], [6, 7, 8], [9, 10]]
[[1, 2, 3, 4, 5], [6, 7, 8, 9], [10]]
[[1, 2, 3, 4, 5, 6], [7], [8, 9, 10]]
[[1, 2, 3, 4, 5, 6], [7, 8], [9, 10]]
[[1, 2, 3, 4, 5, 6], [7, 8, 9], [10]]
[[1, 2, 3, 4, 5, 6, 7], [8], [9, 10]]
[[1, 2, 3, 4, 5, 6, 7], [8, 9], [10]]
[[1, 2, 3, 4, 5, 6, 7, 8], [9], [10]]

Answer 2

对于手动实现，您可以使用递归生成器函数：

def parts(lst, n):
    if 0 < n <= len(lst):
        if n == 1:
            yield [lst]
        else:
            for i in range(1, len(lst)-n+2):
                for part in parts(lst[i:], n-1):
                    yield [lst[:i]] + part



pprint(list(parts([1,2,3,4], 3)))
# [[[1], [2], [3, 4]], 
#  [[1], [2, 3], [4]], 
#  [[1, 2], [3], [4]]]
pprint(list(parts([1,2,3,4,5,6], 3)))
# [[[1], [2], [3, 4, 5, 6]],
#  [[1], [2, 3], [4, 5, 6]],
#  [[1], [2, 3, 4], [5, 6]],
#  [[1], [2, 3, 4, 5], [6]],
#  [[1, 2], [3], [4, 5, 6]],
#  [[1, 2], [3, 4], [5, 6]],
#  [[1, 2], [3, 4, 5], [6]],
#  [[1, 2, 3], [4], [5, 6]],
#  [[1, 2, 3], [4, 5], [6]],
#  [[1, 2, 3, 4], [5], [6]]]

Answer 3

稍微短一点的递归方法：

lst, n = [1,2,3,4,5,6,7,8,9,10], 3
def group(d, c = []):
   if not d and len(c) == n:
      yield c
   if d and c:
       yield from group(d[1:], c[:-1]+[c[-1]+[d[0]]])
   if d and len(c) < n:
       yield from group(d[1:], c+[[d[0]]])

print(list(group(lst)))

输出：

[[[1, 2, 3, 4, 5, 6, 7, 8], [9], [10]], [[1, 2, 3, 4, 5, 6, 7], [8, 9], [10]], [[1, 2, 3, 4, 5, 6, 7], [8], [9, 10]], [[1, 2, 3, 4, 5, 6], [7, 8, 9], [10]], [[1, 2, 3, 4, 5, 6], [7, 8], [9, 10]], [[1, 2, 3, 4, 5, 6], [7], [8, 9, 10]], [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10]], [[1, 2, 3, 4, 5], [6, 7, 8], [9, 10]], [[1, 2, 3, 4, 5], [6, 7], [8, 9, 10]], [[1, 2, 3, 4, 5], [6], [7, 8, 9, 10]], [[1, 2, 3, 4], [5, 6, 7, 8, 9], [10]], [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]], [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]], [[1, 2, 3, 4], [5, 6], [7, 8, 9, 10]], [[1, 2, 3, 4], [5], [6, 7, 8, 9, 10]], [[1, 2, 3], [4, 5, 6, 7, 8, 9], [10]], [[1, 2, 3], [4, 5, 6, 7, 8], [9, 10]], [[1, 2, 3], [4, 5, 6, 7], [8, 9, 10]], [[1, 2, 3], [4, 5, 6], [7, 8, 9, 10]], [[1, 2, 3], [4, 5], [6, 7, 8, 9, 10]], [[1, 2, 3], [4], [5, 6, 7, 8, 9, 10]], [[1, 2], [3, 4, 5, 6, 7, 8, 9], [10]], [[1, 2], [3, 4, 5, 6, 7, 8], [9, 10]], [[1, 2], [3, 4, 5, 6, 7], [8, 9, 10]], [[1, 2], [3, 4, 5, 6], [7, 8, 9, 10]], [[1, 2], [3, 4, 5], [6, 7, 8, 9, 10]], [[1, 2], [3, 4], [5, 6, 7, 8, 9, 10]], [[1, 2], [3], [4, 5, 6, 7, 8, 9, 10]], [[1], [2, 3, 4, 5, 6, 7, 8, 9], [10]], [[1], [2, 3, 4, 5, 6, 7, 8], [9, 10]], [[1], [2, 3, 4, 5, 6, 7], [8, 9, 10]], [[1], [2, 3, 4, 5, 6], [7, 8, 9, 10]], [[1], [2, 3, 4, 5], [6, 7, 8, 9, 10]], [[1], [2, 3, 4], [5, 6, 7, 8, 9, 10]], [[1], [2, 3], [4, 5, 6, 7, 8, 9, 10]], [[1], [2], [3, 4, 5, 6, 7, 8, 9, 10]]]

使用所有组合将列表拆分为 n 个不均匀的桶

Spliting a list into n uneven buckets with all combinations

python

partitioning

list