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

Creating All Possible k Combinations of n Items in C

Given a set of integers from 1 to n, the task is to generate and print all possible combinations of k distinct elements.

Algorithm:

This problem can be solved using a bitmask-based approach. A bitmask is a representation of a number where each bit indicates the presence or absence of an element in the set.

The algorithm works as follows:

1. Generate a bitmask with k leading 1s, representing the first k items in the combination.
2. Resize the bitmask to n bits, with the remaining N-K bits set to 0.
3. Iterate through bitmasks of length n, checking each bit.
4. For each bit set to 1, print the corresponding item.

Code:

#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

Analysis:

This algorithm generates combinations by manipulating bitmasks, which is an efficient way to represent sets of elements. The time complexity is O(n^k) for generating all possible combinations.

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