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 ?

Barbara Streisand
Lepaskan: 2024-11-25 13:34:15
asal
250 orang telah melayarinya

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
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan