Rumah pembangunan bahagian belakang C++ Bagaimana untuk Menjana Semua K-Kombinasi daripada N Elements dalam C ?

Bagaimana untuk Menjana Semua K-Kombinasi daripada N Elements dalam C ?

Nov 25, 2024 pm 01:34 PM

How to Generate All K-Combinations from N Elements in C  ?

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

  1. Perwakilan Binari: Setiap gabungan boleh diwakili sebagai rentetan binari, di mana bit set menunjukkan kehadiran yang sepadan elemen.
  2. Permulaan Bitmask: Cipta rentetan binari dengan k mendahului 1s dan N-k mengekor 0s.
  3. Pindaan: Lelaran melalui semua pilih atur yang mungkin bagi rentetan binari ini menggunakan STL prev_permutation fungsi.
  4. 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);
}
Salin selepas log masuk

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
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes Langkah Format Fungsi Fungsi C Langkah Penukaran Kes Mar 03, 2025 pm 05:53 PM

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes

Gulc: Perpustakaan C dibina dari awal Gulc: Perpustakaan C dibina dari awal Mar 03, 2025 pm 05:46 PM

Gulc: Perpustakaan C dibina dari awal

Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan? Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan? Mar 03, 2025 pm 05:52 PM

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 Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu Mar 03, 2025 pm 05:53 PM

Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi? Bagaimana Perpustakaan Templat St Standard (STL) berfungsi? Mar 12, 2025 pm 04:50 PM

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi?

Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan? Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan? Mar 03, 2025 pm 05:51 PM

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

Penggunaan dan perkongsian frasa yang berbeza Penggunaan dan perkongsian frasa yang berbeza Mar 03, 2025 pm 05:51 PM

Penggunaan dan perkongsian frasa yang berbeza

Berapakah minimum biasa dari pembahagi umum maksimum fungsi bahasa C? Berapakah minimum biasa dari pembahagi umum maksimum fungsi bahasa C? Mar 03, 2025 pm 05:55 PM

Berapakah minimum biasa dari pembahagi umum maksimum fungsi bahasa C?

See all articles