如何在 Python 中将一个集合划分为其所有可能的子集？

Python 中的分区集

当前的任务是将给定的元素集分区为所有可能的子集。例如，对集合 [1, 2, 3] 进行分区会产生以下子集：

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

递归解决方案

解决此问题的一种方法是递归。给定一个包含 n-1 个元素的分区，我们可以通过将第 n 个元素包含在现有子集中之一或创建一个仅包含第 n 个元素的新单例子集来扩展它以创建 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` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller

something = list(range(1,5))

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

以上是如何在 Python 中将一个集合划分为其所有可能的子集？的详细内容。更多信息请关注PHP中文网其他相关文章！