Bagaimana untuk Menjana Semua K-Kombinasi daripada N Elements dalam 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);
}

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!