Home >Backend Development >C++ >How to Generate All Possible k Combinations of n Items in C ?

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

DDD
DDDOriginal
2024-11-22 07:42:18759browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn