如何在 Python 中生成数组的所有可能的集合分区？

Python 中的设置分区

将数组划分为不同的子集，其中每个元素恰好属于一个子集，称为集合分区。给定一个元素数组，我们如何使用 Python 生成所有可能的集合分区？

考虑一个数组 [1, 2, 3]。我们的目标是获得以下分区：

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

递归解决方案

我们的解决方案利用递归来实现此分区。对于 n-1 个元素的分区，我们考虑两种选择来容纳第 n 个元素：

1. 将第 n 个元素添加到现有子集中。
2. 创建一个仅包含第 n 个元素。

通过迭代应用这些选项，我们可以构造所有可能的分区。

实现

<code class="python">def partition(collection):
    if len(collection) == 1:
        yield [collection]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # Insert first into existing subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n+1:]
        # Create a new subset
        yield [[first]] + smaller


something = list(range(1, 5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))</code>

输出

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

该解决方案有效地生成给定数组的所有可能的集合分区。

以上是如何在 Python 中生成数组的所有可能的集合分区？的详细内容。更多信息请关注PHP中文网其他相关文章！