How to Generate All Possible Set Partitions of an Array in Python?

Set Partitions in Python

Dividing an array into distinct subsets, where each element belongs to exactly one subset, is known as set partitioning. Given an array of elements, how can we generate all possible set partitions using Python?

Consider an array [1, 2, 3]. We aim to obtain the following partitions:

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

Recursive Solution

Our solution leverages recursion to achieve this partitioning. For a partition of n-1 elements, we consider two options for accommodating the nth element:

1. Adding the nth element to an existing subset.
2. Creating a new subset containing only the nth element.

By iteratively applying these options, we can construct all possible partitions.

Implementation

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

Output

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

This solution effectively generates all possible set partitions of the given array.

The above is the detailed content of How to Generate All Possible Set Partitions of an Array in Python?. For more information, please follow other related articles on the PHP Chinese website!