C에서 n 항목의 가능한 모든 k 조합을 생성하는 방법은 무엇입니까?

C에서 n 항목의 가능한 모든 k 조합 생성

1부터 n까지의 정수 집합이 주어지면 작업은 다음을 생성하는 것입니다. k개의 가능한 모든 조합을 인쇄합니다. elements.

알고리즘:

이 문제는 비트마스크 기반 접근 방식을 사용하여 해결할 수 있습니다. 비트마스크는 각 비트가 집합에 있는 요소의 존재 여부를 나타내는 숫자 표현입니다.

알고리즘은 다음과 같이 작동합니다.

1. k를 앞에 두고 비트마스크를 생성합니다. 1s, 조합의 첫 번째 k 항목을 나타냅니다.
2. 비트마스크 크기를 n 비트로 조정하고 나머지 N-K 비트는 다음으로 설정합니다. 0.
3. 길이 n의 비트마스크를 반복하여 각 비트를 확인합니다.
4. 1로 설정된 각 비트에 대해 해당하는 것을 인쇄합니다. item.

코드:

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

출력:

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

분석:

이 알고리즘은 조합을 생성합니다. 요소 세트를 표현하는 효율적인 방법인 비트마스크를 조작함으로써 가능합니다. 가능한 모든 조합을 생성하기 위한 시간 복잡도는 O(n^k)입니다.

위 내용은 C에서 n 항목의 가능한 모든 k 조합을 생성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!