Bagaimanakah anda boleh menjana semua subset set menggunakan algoritma rekursif?

Menjana Semua Subset Set

Dalam menentukan semua subset bagi set tertentu, bilangan elemen (n) memainkan peranan penting . Algoritma yang berkesan memanfaatkan teknik rekursif untuk mencapainya.

Algoritma Rekursif

Algoritma rekursif beroperasi berdasarkan prinsip bahawa, bagi setiap elemen, subset boleh dibahagikan kepada dua kategori: yang mengandungi unsur dan yang mengecualikannya. Kedua-dua partition ini berkongsi subset yang sama sebaliknya.

Bermula dengan n=1, kami mempunyai dua subset: {} (set kosong) dan {1}.

Untuk n>1, kami tentukan subset bagi 1,...,n-1 dan salinkannya. Satu set akan mempunyai n ditambahkan pada setiap subset, manakala satu lagi akan kekal tidak berubah. Penyatuan kedua-dua set ini menghasilkan set lengkap subset.

Contoh Ilustrasi

Mari kita hasilkan subset {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: Ambil {} , {1} dan tambah 2. Union dengan {} , {1}: {{} , {1} , { 2} , {1, 2}}
• n=3: Tambah 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: Tambah 4: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}}
• n=5: Tambah 5: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2 , 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}, {5} , {1, 5} , {2, 5} , {1, 2, 5} , {3, 5} , {1, 3, 5} , {2, 3, 5} , {1, 2, 3, 5}, {4, 5} , {1, 4, 5} , {2, 4, 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4, 5}}

Oleh itu, kami tiba di kesemua 32 subset {1, 2, 3, 4, 5}.

Atas ialah kandungan terperinci Bagaimanakah anda boleh menjana semua subset set menggunakan algoritma rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!