python - 如何获得具有每个子集的最大大小限制的列表的所有可能的 set partition ?

这是我想要做的。给定一个数字 k 和一个 set 数字,我希望 partition 和 set 元素的大小不大于 k。

例如)lst = [1, 2, 3, 4], k=2

lst的所有可能的set partition如下。代码在下面的上一个问题中:(https://stackoverflow.com/questions/19368375/set-partitions-in-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]]

但是,每个 partition 的每个元素的大小不应超过 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 中会有算法吗?

回答1

按长度过滤您在 https://stackoverflow.com/questions/19368375/set-partitions-in-python 中发布的答案的结果。例如,如果您想避免技术性(不在标准库中),请使用 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]]

相似文章

最新文章