Bagaimanakah Anda Boleh Membahagikan Set Kepada Semua Subset yang Mungkin dalam 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!