How to Generate All k Combinations of n Items in C ?

Algorithm to Generate All k Combinations of n Items in C

The task at hand is to create a program that generates and displays all possible combinations of k distinct people from a set of n individuals. This can be achieved using a combination-generating algorithm, which operates as follows:

Algorithm:

1. Initialize a bitmask with a sequence of K leading 1s: This bitmask signifies that the first K people in the set are initially assigned to the combination.
2. Resize the bitmask to N bits, appending N-K trailing 0s: This step extends the bitmask to cover all n people in the set.
3. Iterate through all possible permutations of the bitmask: Each permutation represents a different combination of K people.

4. For each permutation:

   • Extract the indices of the set bits in the bitmask. These indices represent the members of the current combination.
   • Print out the combination.
5. Repeat step 3 until all permutations have been exhausted: This will have generated all possible combinations of K people from the set of n.

Implementation in 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);
}

Sample 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

The above is the detailed content of How to Generate All k Combinations of n Items in C ?. For more information, please follow other related articles on the PHP Chinese website!