Rumah >pembangunan bahagian belakang >Tutorial Python >Bagaimanakah Anda Boleh Membahagikan Set Kepada Semua Subset yang Mungkin dalam Python?

Bagaimanakah Anda Boleh Membahagikan Set Kepada Semua Subset yang Mungkin dalam Python?

DDD
DDDasal
2024-11-07 16:43:03883semak imbas

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

Set Pembahagian dalam Python

Tugas di tangan ialah membahagikan set elemen yang diberikan kepada semua subset yang mungkin. Contohnya, pembahagian set [1, 2, 3] menghasilkan subset berikut:

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

Penyelesaian Rekursif

Satu pendekatan untuk masalah ini ialah rekursi. Memandangkan partition elemen n-1, kita boleh memanjangkannya untuk mencipta partition bagi n elemen dengan sama ada memasukkan elemen ke-n dalam salah satu subset sedia ada atau mencipta subset tunggal baharu yang mengandungi hanya elemen ke-n.

Algoritma rekursif ini membahagikan set input dengan berkesan sambil mengelakkan output pendua dan kebergantungan yang tidak perlu pada perpustakaan luaran:

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

Atas ialah kandungan terperinci Bagaimanakah Anda Boleh Membahagikan Set Kepada Semua Subset yang Mungkin dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn