Bagaimanakah saya boleh menjana semua subset set menggunakan algoritma rekursif?

Mencari Semua Subset Set Menggunakan Algoritma Rekursif

Memandangkan set dengan n elemen, mencari semua subset yang mungkin adalah tugas biasa. Artikel ini membentangkan penjelasan langkah demi langkah tentang algoritma rekursif yang cekap untuk mencapainya.

Pendekatan Rekursif

Algoritma adalah berdasarkan idea bahawa untuk setiap elemen dalam satu set, terdapat dua kemungkinan:

1. Sertakan elemen: Ini mencipta subset baharu yang merangkumi elemen.
2. Kecualikan elemen: Ini mencipta subset baharu yang mengecualikan elemen.

Dengan mempertimbangkan kedua-dua kemungkinan untuk setiap elemen, kami meliputi semua kombinasi yang mungkin dan oleh itu mencari semua subset.

Penjelasan Langkah demi Langkah

Mari kita ambil set {1, 2, 3, 4, 5} sebagai contoh.

1. Kes Asas: Untuk n=1, set mempunyai satu elemen (cth., {1}). Subset ialah {{}} (set kosong) dan {{1}} (hanya mengandungi 1).

2. Kes Rekursif: Untuk n>1, kita boleh memecahkan masalah itu dibahagikan kepada dua submasalah:

   • Cari subset {1, 2, 3, 4, 5-1}: Kami memanggil algoritma secara rekursif untuk elemen n-1 pertama dan mendapatkan set subset.
   • Buat dua salinan set subset: Satu salinan adalah untuk memasukkan unsur n dalam setiap subset, dan satu lagi adalah untuk mengecualikannya.
   • Tambahkan n pada subset dalam salinan sertakan: Contohnya, jika kita mempunyai {{}, {1}, {2}}, menambah 5 akan memberikan {{}, {1}, {2}, {5}, {1, 5}, {2, 5}}.
   • Ambil gabungan dua salinan: Ini memberi kita set lengkap subset.

Contoh

Mari kita hitung subset {1, 2, 3, 4, 5} secara rekursif:

• Langkah 1 (n=1): Subset = {{}, {1}}
• Langkah 2 (n=2): Subset = {{}, {1}, { 2}, {1, 2}} (buat salinan untuk {2})
• Langkah 3 (n=3): Subset = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}} (tambah 3 pada { 2} salinan)
• Langkah 4 (n=4): Subset = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}} (tambah 4 kepada salinan {3})
• Langkah 5 (n=5): Subset = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4} , {5}, {1, 5}, {2, 5}, {1, 2, 5}} (tambah 5 pada {4} salinan)

Oleh itu, set lengkap subset ialah {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 5}}.

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