How to Generate All K-Combinations from N Elements in C ?

Combinatorial Generation: Constructing Combinations in C

Combinations are sets of elements that lack order, and in this article, we focus on generating all possible k combinations from a set of n elements.

Algorithm

The provided C code employs a straightforward algorithm:

1. Binary Representation: Each combination can be represented as a binary string, where a set bit indicates the presence of the corresponding element.
2. Bitmask Initialization: Create a binary string with k leading 1s and N-k trailing 0s.
3. Permutation: Iterate through all possible permutations of this binary string using the STL prev_permutation function.
4. Output: For each permutation, print the indices of the elements corresponding to the set bits.

Code Implementation

#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

Analysis

This algorithm takes advantage of the one-to-one correspondence between binary strings and combinations. By permuting the binary representation, it effectively generates all possible bitmask combinations and hence all possible combinations of the elements.

The complexity of this algorithm is O(C(n, k)), where C(n, k) is the number of combinations of n items taken k at a time.

The above is the detailed content of How to Generate All K-Combinations from N Elements in C ?. For more information, please follow other related articles on the PHP Chinese website!