비트 조작을 사용하여 C에서 조합을 효율적으로 생성하려면 어떻게 해야 합니까?-C++-php.cn

비트 조작을 사용하여 C에서 조합을 효율적으로 생성하려면 어떻게 해야 합니까?

Linda Hamilton

풀어 주다： 2024-11-29 04:14:11

원래의

917명이 탐색했습니다.

How Can I Efficiently Generate Combinations in C Using Bit Manipulation?

C에서 조합 생성: 포괄적인 솔루션

조합 생성은 집합에서 특정 개수의 요소를 선택하는 기본 프로그래밍 작업입니다. . 예를 들어 S = {1, 2, 3, 4, 5} 집합이 있고 크기 r = 2의 조합을 생성하려는 경우 출력에는 (1, 2), (1, 3)과 같은 조합이 포함됩니다. ), (2, 3) 등이 있습니다.

C를 사용하여 조합을 생성하는 효과적인 방법 중 하나는 비트 조작을 사용하는 것입니다. 집합 요소를 나타내는 길이 n의 부울 벡터를 초기화한 다음 첫 번째 r개 요소를 true로 채울 수 있습니다. 이는 현재 조합에서 해당 요소가 선택되었음을 의미합니다.

다음 단계는 std::next_permutation 함수를 사용하여 이 선택 벡터의 모든 순열을 생성하는 것입니다. 각 순열에 대해 요소가 선택되었는지(벡터의 참값으로 표시됨) 확인하고 해당 요소를 인쇄합니다. 모든 순열을 반복함으로써 가능한 모든 조합을 생성할 수 있습니다.

다음은 이 접근 방식을 사용하는 코드 조각입니다.

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

로그인 후 복사

또는 std::prev_permutation 함수를 사용하여 조합을 생성할 수 있습니다. 오름차순:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

로그인 후 복사

이러한 기술을 활용하여 다양한 알고리즘 애플리케이션을 위한 강력한 도구를 제공하여 C에서 조합을 효율적으로 생성할 수 있습니다.

위 내용은 비트 조작을 사용하여 C에서 조합을 효율적으로 생성하려면 어떻게 해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!