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

C에서 n 항목의 모든 k 조합을 생성하는 알고리즘

당면 작업은 가능한 모든 항목을 생성하고 표시하는 프로그램을 만드는 것입니다. n개의 개인 집합에서 k개의 서로 다른 사람들의 조합. 이는 다음과 같이 작동하는 조합 생성 알고리즘을 사용하여 달성할 수 있습니다.

알고리즘:

1. K 시퀀스로 비트마스크를 초기화합니다. 선행 1: 이 비트마스크는 집합의 첫 번째 K명이 처음에 할당됨을 나타냅니다. 조합.
2. 비트마스크 크기를 N 비트로 조정하고 N-K 뒤에 0을 추가합니다. 이 단계는 비트마스크를 확장하여 세트의 모든 n명을 포괄합니다.
3. 반복 비트마스크의 가능한 모든 순열을 통해: 각 순열은 K의 다른 조합을 나타냅니다. people.

4. 각 순열에 대해:

   • 비트마스크에서 설정된 비트의 인덱스를 추출합니다. 이 색인은 현재 조합의 구성원을 나타냅니다.
   • 조합을 인쇄합니다.
5. 모든 순열이 소진될 때까지 3단계를 반복합니다. 집합에서 K명의 가능한 모든 조합을 생성했을 것입니다. n.

C로 구현:

#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

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