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中文網其他相關文章!