Bagaimana untuk Menjana Semua Partition Set Kemungkinan Array dalam Python?

Tetapkan Pemisahan dalam Python

Membahagikan tatasusunan kepada subset yang berbeza, di mana setiap elemen tergolong dalam satu subset, dikenali sebagai pembahagian set. Memandangkan tatasusunan elemen, bagaimanakah kita boleh menjana semua partition set yang mungkin menggunakan Python?

Pertimbangkan tatasusunan [1, 2, 3]. Kami berhasrat untuk mendapatkan partition berikut:

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

Penyelesaian Rekursif

Penyelesaian kami memanfaatkan rekursi untuk mencapai pembahagian ini. Untuk partition elemen n-1, kami mempertimbangkan dua pilihan untuk menampung elemen ke-n:

1. Menambah elemen ke-n pada subset sedia ada.
2. Mencipta subset baharu yang mengandungi hanya elemen ke-n.

Dengan menggunakan pilihan ini secara berulang, kami boleh membina semua partition yang mungkin.

Pelaksanaan

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

Output

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

Penyelesaian ini berkesan menjana semua partition set yang mungkin bagi tatasusunan yang diberikan.

Atas ialah kandungan terperinci Bagaimana untuk Menjana Semua Partition Set Kemungkinan Array dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!