首頁  >  文章  >  後端開發  >  如何在 Python 中將一個集合劃分為其所有可能的子集?

如何在 Python 中將一個集合劃分為其所有可能的子集?

DDD
DDD原創
2024-11-07 16:43:03817瀏覽

How Can You Partition a Set Into All Its Possible Subsets in 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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn