[c++] 순열과 조합 알고리즘

12 Dec 2023

이 문서에서는 C++를 사용하여 주어진 요소 집합에 대한 순열(permutation)과 조합(combination)을 생성하는 방법에 대해 다룹니다.

순열(permutation)

순열은 요소 집합의 순서를 바꿔 나열한 결과를 의미합니다. 예를 들어, {1, 2, 3}의 순열은 {1, 2, 3}, {1, 3, 2}, {2, 1, 3} 등이 됩니다.

아래는 C++ 표준 라이브러리인 <algorithm>을 사용하여 순열을 생성하는 예제 코드입니다.

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

int main() {
    std::vector<int> elements = {1, 2, 3};

    do {
        for (int element : elements) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(elements.begin(), elements.end()));

    return 0;
}

std::next_permutation 함수는 주어진 벡터의 다음 순열을 생성하고, 다음 순열이 없을 경우 false를 반환합니다.

조합(combination)

조합은 요소 집합에서 일부 요소를 선택하여 만들어지는 부분집합을 의미합니다. 예를 들어, {1, 2, 3}에서 2개의 조합은 {1, 2}, {1, 3}, {2, 3} 등이 됩니다.

아래는 재귀 함수를 사용하여 모든 조합을 생성하는 예제 코드입니다.

#include <iostream>
#include <vector>

void generateCombinations(std::vector<int>& elements, std::vector<int>& combination, int startIndex, int k) {
    if (k == 0) {
        for (int element : combination) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
        return;
    }

    for (int i = startIndex; i < elements.size(); ++i) {
        combination.push_back(elements[i]);
        generateCombinations(elements, combination, i + 1, k - 1);
        combination.pop_back();
    }
}

int main() {
    std::vector<int> elements = {1, 2, 3};
    int k = 2;
    std::vector<int> combination;

    generateCombinations(elements, combination, 0, k);

    return 0;
}

위의 코드는 조합을 생성하는 재귀 함수인 generateCombinations를 정의하고, 해당 함수를 호출하여 모든 조합을 출력합니다.

이러한 알고리즘을 사용하여 순열과 조합을 생성할 수 있습니다.

참고 문헌: