C의 N 요소에서 모든 K-조합을 생성하는 방법은 무엇입니까?

조합 생성: C에서 조합 생성

조합은 순서가 없는 요소의 집합이며, 이 문서에서는 모든 항목을 생성하는 데 중점을 둡니다. n개의 집합에서 가능한 k개의 조합 요소.

알고리즘

제공된 C 코드는 간단한 알고리즘을 사용합니다.

1. 이진 표현: 각 조합 이진 문자열로 표현될 수 있으며, 여기서 세트 비트는 해당 문자열의 존재를 나타냅니다. 요소.
2. 비트마스크 초기화: k 선행 1과 N-k 후행 0으로 이진 문자열을 생성합니다.
3. 순열: 다음의 가능한 모든 순열을 반복합니다. STL prev_permutation을 사용하는 이 바이너리 문자열 function.
4. 출력: 각 순열에 대해 설정된 비트에 해당하는 요소의 인덱스를 인쇄합니다.

코드 구현

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

출력

 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(C(n, k))입니다. 여기서 C(n, k )는 n개 항목을 한번에 k개 취하는 조합의 개수입니다.

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