


Bagaimana untuk Menjana Semua K-Kombinasi daripada N Elements dalam C ?
Nov 25, 2024 pm 01:34 PMPenjanaan Kombinatorial: Membina Gabungan dalam C
Kombinasi ialah set elemen yang kurang tertib, dan dalam artikel ini, kami menumpukan pada penjanaan semua kemungkinan k gabungan daripada set n elemen.
Algoritma
Kod C yang disediakan menggunakan algoritma mudah:
- Perwakilan Binari: Setiap gabungan boleh diwakili sebagai rentetan binari, di mana bit set menunjukkan kehadiran yang sepadan elemen.
- Permulaan Bitmask: Cipta rentetan binari dengan k mendahului 1s dan N-k mengekor 0s.
- Pindaan: Lelaran melalui semua pilih atur yang mungkin bagi rentetan binari ini menggunakan STL prev_permutation fungsi.
- Output: Untuk setiap pilih atur, cetak indeks elemen yang sepadan dengan bit yang ditetapkan.
Kod Pelaksanaan
#include <algorithm> #include <iostream> #include <string> void comb(int N, int K) { std::string bitmask(K, 1); // K leading 1's bitmask.resize(N, 0); // N-K trailing 0's // print integers and permute bitmask do { for (int i = 0; i < N; ++i) // [0..N-1] integers { if (bitmask[i]) std::cout << " " << i; } std::cout << std::endl; } while (std::prev_permutation(bitmask.begin(), bitmask.end())); } int main() { comb(5, 3); }
Output
0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 4
Analisis
Algoritma ini mengambil kesempatan daripada satu- ke-satu surat-menyurat antara rentetan binari dan gabungan. Dengan mengubah suai perwakilan binari, ia menjana semua gabungan bitmask yang mungkin dan seterusnya semua gabungan elemen yang mungkin.
Kerumitan algoritma ini ialah O(C(n, k)), di mana C(n, k ) ialah bilangan gabungan n item yang diambil k pada satu masa.
Atas ialah kandungan terperinci Bagaimana untuk Menjana Semua K-Kombinasi daripada N Elements dalam C ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Artikel Panas

Alat panas Tag

Artikel Panas

Tag artikel panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes

Gulc: Perpustakaan C dibina dari awal

Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan?

Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi?

Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan?

Penggunaan dan perkongsian frasa yang berbeza

Berapakah minimum biasa dari pembahagi umum maksimum fungsi bahasa C?
