Enumerasi Subset dengan Bitmask
Ulangi semua subset melalui integer.
Enumerasi Subset dengan Bitmask ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Subhimpunan sebagai Nombor
Setiap subhimpunan yang terdiri daripada n item boleh dipetakan kepada satu integer. Kira dari 0 ke atas, dan bit bagi setiap nombor memilih tepat item yang disertakan. 🙂
Bilangan Subhimpunan
Satu set yang mengandungi n item mempunyai 2^n subhimpunan. Jadi, mengulang nombor bulat dari 0 hingga 2^n tolak 1 akan melalui setiap subhimpunan tepat sekali.
for mask in range(1 << n):
pass # mask is one subset1 << n Ialah Bilangan
Anjakan 1 << n bersamaan dengan 2 kuasa n. Inilah cara yang kemas dan pantas untuk menulis had atas gelung subhimpunan Anda.
Baca Bit i
Untuk menyemak sama ada item i termasuk dalam subhimpunan, uji bit-nya menggunakan mask dan 1 yang dianjak ke kiri sebanyak i. Hasil bukan sifar bermaksud item itu termasuk.
if mask & (1 << i):
take(items[i])Bina Senarai yang Dipilih
Telusuri setiap kedudukan bit dan kumpulkan item yang bitnya ditetapkan. Dengan itu, satu mask ditukarkan kepada subhimpunan nyata yang diwakilinya.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Set Kosong dan Penuh
Mask 0 ialah subhimpunan kosong, manakala mask yang semua bitnya bernilai satu ialah set penuh. Kedua-duanya tersedia secara automatik kerana gelung Anda meliputi setiap nilai.
Jumlahkan Subhimpunan
Dalam gelung, jumlahkan item yang dipilih untuk memberikan skor kepada setiap subhimpunan. Inilah teras banyak penyelesaian kecil menggunakan kaedah cuba semua.
total = sum(v[i] for i in range(n) if mask & (1 << i))Kira Bit yang Ditetapkan
Bilangan item yang dipilih bersamaan dengan bilangan bit 1 dalam mask. Dalam Python, bin(mask).count('1') memberikan jawapannya serta-merta.
size = bin(mask).count("1")Perhatikan Had
Memandangkan terdapat 2^n subhimpunan, teknik ini hanya sesuai untuk n yang kecil. Sekitar n bersamaan 20 ialah had praktikal untuk enumerasi penuh.
Mengapa Topeng Bit Menang
Satu gelung nombor bulat menggantikan gelung bersarang yang berserabut, dan operasi bit adalah pantas. Kod kekal ringkas, jelas dan mudah diuji.
Corak yang Boleh Digunakan Semula
Ulang melalui mask, nyahkod bitnya, berikan skor kepada subhimpunan dan simpan yang terbaik. Hafalkan templat ini, dan banyak masalah subhimpunan akan menjadi rutin.
Semakan Pantas
Anda mahu menguji sama ada item i termasuk dalam subhimpunan yang dikodkan oleh mask.
Ulang Kaji
Ulang mask dari 0 hingga 2^n tolak 1, baca bit menggunakan mask dan 1 yang dianjak ke kiri, kemudian berikan skor kepada setiap subhimpunan. Inilah kaedah cuba semua yang kemas untuk n yang kecil. 🚀
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Enumerasi Subset dengan Bitmask” percuma?
Ya — teks penuh “Enumerasi Subset dengan Bitmask” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Enumerasi Subset dengan Bitmask”?
Ulangi semua subset melalui integer. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Enumerasi Subset dengan Bitmask” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Brute Force ialah Strategi yang Sah
- Enumerasi dengan itertools
- Enumerasi Subset dengan Bitmask
- Kecilkan Ruang Carian dengan Bijak