如何在 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中文網其他相關文章！