Bagaimana Menjana Semua Kemungkinan k Gabungan n Item dalam C ?

Mencipta Semua Kemungkinan k Gabungan n Item dalam C

Memandangkan set integer dari 1 hingga n, tugasnya adalah untuk menjana dan cetak semua kemungkinan kombinasi k yang berbeza elemen.

Algoritma:

Masalah ini boleh diselesaikan menggunakan pendekatan berasaskan bitmask. Bitmask ialah perwakilan nombor di mana setiap bit menunjukkan kehadiran atau ketiadaan elemen dalam set.

Algoritma berfungsi seperti berikut:

1. Janakan bitmask dengan petunjuk k 1s, mewakili k item pertama dalam gabungan.
2. Ubah saiz topeng bit kepada n bit, dengan baki N-K bit ditetapkan kepada 0.
3. Lelar melalui bitmask dengan panjang n, semak setiap bit.
4. Untuk setiap bit yang ditetapkan kepada 1, cetak yang sepadan item.

Kod:

#include <algorithm>
#include <iostream>
#include <string>

void comb(int N, int K)
{
    std::string bitmask(K, 1);
    bitmask.resize(N, 0);

    do {
        for (int i = 0; i < N; ++i) {
            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 menghasilkan kombinasi dengan memanipulasi bitmasks, iaitu cara yang cekap untuk mewakili set elemen. Kerumitan masa ialah O(n^k) untuk menjana semua gabungan yang mungkin.

Atas ialah kandungan terperinci Bagaimana Menjana Semua Kemungkinan k Gabungan n Item dalam C ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!