Bagaimana untuk Menjana Semua k Gabungan n Item dalam C?

Algoritma untuk Menjana Kesemua k Gabungan n Item dalam C

Tugas di tangan adalah untuk mencipta program yang menjana dan memaparkan semua yang mungkin gabungan k orang yang berbeza daripada satu set n individu. Ini boleh dicapai menggunakan algoritma penjanaan gabungan, yang beroperasi seperti berikut:

Algoritma:

1. Mulakan bitmask dengan urutan K mendahului 1: Bitmask ini menandakan bahawa orang K pertama dalam set pada mulanya diberikan kepada gabungan.
2. Ubah saiz bitmask kepada N bit, menambahkan N-K mengekor 0s: Langkah ini memanjangkan bitmask untuk meliputi semua n orang dalam set.
3. Lelaran melalui semua pilih atur yang mungkin bagi bitmask: Setiap pilih atur mewakili gabungan K orang yang berbeza.

4. Untuk setiap pilih atur:

   • Ekstrak indeks bit set dalam bitmask. Indeks ini mewakili ahli gabungan semasa.
   • Cetak gabungan.
5. Ulang langkah 3 sehingga semua pilih atur telah habis: Ini akan menghasilkan semua kemungkinan gabungan orang K daripada set n.

Pelaksanaan dalam C :

#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);
}

Sampel 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

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