如何获得每个子集的最大尺寸限制列表的所有可能的设置分区？

Question

这是我想做的。给定数字k和一组数字，我想用大小不大于k大的元素来划分集合。

ex）lst = [1，2，3，4]，k = 2

LST的所有可能的设置分区如下。代码在下面的上一个问题中： （在Python中设置分区）

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

但是，每个分区的大小不应超过k = 2。 任何子集具有超过k = 2个元素的所有情况均应删除。 因此，结果应该如下：

3 [[1, 2], [3, 4]]
5 [[1], [2], [3, 4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

Python中会有算法吗？

Answer 1

过滤 link 您提供的答案的结果。例如，使用more_itertools.set_partitions如果要避免技术性（不在标准库中）。

p = [[[1, 2, 3, 4]],
[[1], [2, 3, 4]],
[[1, 2], [3, 4]],
[[1, 3, 4], [2]],
[[1], [2], [3, 4]],
[[1, 2, 3], [4]],
[[1, 4], [2, 3]],
[[1], [2, 3], [4]],
[[1, 3], [2, 4]],
[[1, 2, 4], [3]],
[[1], [2, 4], [3]],
[[1, 2], [3], [4]],
[[1, 3], [2], [4]],
[[1, 4], [2], [3]],
[[1], [2], [3], [4]]]

def filter_partition(partitions, k):
   return [p for p in partitions if all(len(block)<=k for block in p)]


print(*filter_partition(p, 2), sep='\n')

输出

[[1, 2], [3, 4]]
[[1], [2], [3, 4]]
[[1, 4], [2, 3]]
[[1], [2, 3], [4]]
[[1, 3], [2, 4]]
[[1], [2, 4], [3]]
[[1, 2], [3], [4]]
[[1, 3], [2], [4]]
[[1, 4], [2], [3]]
[[1], [2], [3], [4]]