How Can You Partition a Set Into All Its Possible Subsets in Python?

Partitioning Sets in Python

The task at hand is to partition a given set of elements into all possible subsets. For instance, partitioning the set [1, 2, 3] yields the following subsets:

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

Recursive Solution

One approach to this problem is recursion. Given a partition of n-1 elements, we can extend it to create a partition of n elements by either including the nth element in one of the existing subsets or creating a new singleton subset containing only the nth element.

This recursive algorithm effectively partitions the input set while avoiding duplicate outputs and unnecessary dependencies on external libraries:

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

The above is the detailed content of How Can You Partition a Set Into All Its Possible Subsets in Python?. For more information, please follow other related articles on the PHP Chinese website!