(C++) 순열과 조합 정리

순열

💡순열(Permutation)이란 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것이다.

재귀를 이용한 방법 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

void permutation(vector<int> &arr, int depth, int n, int r)
{
    if (depth == r)
    {
        for (int i = 0; i < r; i++)
            cout << arr[i] << " ";
        cout << '\\n';

        return;
    }

    for (int i = depth; i < n; i++)
    {
        swap(arr[depth], arr[i]);
        permutation(arr, depth + 1, n, r); // 재귀
        swap(arr[depth], arr[i]);
    }
}

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

    vector<int> v;
    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    permutation(v, 0, n, r);
}

https://chanho0912.tistory.com/15

 

재귀를 이용한 방법 2 (중복 검사)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

void permutation(vector<int> &arr, vector<bool> &check, vector<int> &perm, int depth)
{
    if (depth == perm.size()) // r
    {
        for (int i = 0; i < perm.size(); i++)
            cout << perm[i] << " ";
        cout << '\\n';

        return;
    }

    for (int i = 0; i < arr.size(); i++)
    {
        if (!check[i])
        {
            check[i] = true;
            perm[depth] = i + 1;
            permutation(arr, check, perm, depth + 1);
            check[i] = false;
        }
    }
}

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

    vector<int> v;
    vector<int> perm(r);
    vector<bool> check(n + 1);

    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    permutation(v, check, perm, 0);
}

STL을 이용한 방법

C++/STL에서 제공하는 next_permutation을 이용해서 순열을 사용할 수 있다. next_parmutation은 오름차순 정렬이 되어 있을 때 사용이 가능하다. 내림차순 정렬이 되어 있다면 prev_permutation을 사용한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

int main()
{
    int n;
    cin >> n;

    vector<int> v;

    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    sort(v.begin(), v.end()); // ★

    do {
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
        }
        cout << '\\n';
    } while (next_permutation(v.begin(), v.end()));
}

그러나 이렇게 사용한다면 항상 n!의 값만 나온다. nPr 형식으로 출력하고 싶다면 다음과 같이 사용한다.

do {
        for (int i = 0; i < r; i++)
        {
            cout << v[i] << " ";
        }
        cout << '\\n';
        reverse(v.begin() + r, v.end()); // ★
} while (next_permutation(v.begin(), v.end()));

조합

💡조합(Combination)은 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것이다.

→ 조합은 순열과 다르게 방문 체크, 복원이 필요 없다. 조합에서는 abc와 bca가 같다. 그러므로 b로 시작하는 모든 조합에 a가 포함되지 않는다. b 이후의 원소들에서만 포함 여부를 따지기 때문이다.

재귀를 이용한 방법 1

조합을 구할 땐, nCr = n-1Cr-1 + n-1Cr 공식을 사용하여 재귀적으로 구한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

void combination(vector<int>& arr, vector<int>& comb, int r, int index, int depth)
{
    if (r == 0)
    {
        for (int i = 0; i < comb.size(); i++)
        {
            cout << comb[i] << " ";
        }
        cout << '\\n';
    }
    else if (depth == arr.size()) // depth == n. r개를 채우지 못한 경우는 return
        return;
    else
    {
        // arr[depth]를 뽑은 경우
        comb[index] = arr[depth];
        combination(arr, comb, r - 1, index + 1, depth + 1);

        // arr[depth]를 뽑지 않은 경우
        combination(arr, comb, r, index, depth + 1);
    }
}

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

    vector<int> v;
    vector<int> comb(r);

    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    combination(v, comb, r, 0, 0);
}

재귀를 이용한 방법 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

void combination(vector<int>& arr, vector<int>& comb, int index, int depth)
{
    if (depth == comb.size())
    {
        for (int i = 0; i < comb.size(); i++)
        {
            cout << comb[i] << " ";
        }
        cout << '\\n';
        return;
    }

    for (int i = index; i < arr.size(); i++)
    {
        comb[depth] = arr[i];
        combination(arr, comb, i + 1, depth + 1);
    }
}

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

    vector<int> v;
    vector<int> comb(r);

    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    combination(v, comb, 0, 0);
}

STL을 이용한 방법

next_permutaton으로 구하기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

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

    vector<int> v;
    vector<int> visited(n, true);

    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    for (int i = 0; i < v.size() - r; i++)
        visited[i] = false; 

    do {
        for (int i = 0; i < v.size(); i++)
        {
            if (visited[i])
                cout << v[i] << " ";
        }
        cout << '\\n';
    } while (next_permutation(visited.begin(), visited.end())); // ★
}

prev_permutation으로 구하기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

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

    vector<int> v;
    vector<int> visited(n);

    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }

    for (int i = 0; i < r; i++)
        visited[i] = true; // bool 배열 초기 상태가 내림차순 정렬

    do {
        for (int i = 0; i < v.size(); i++)
        {
            if (visited[i])
                cout << v[i] << " ";
        }
        cout << '\\n';
    } while (prev_permutation(visited.begin(), visited.end())); // ★
}

> 재귀함수를 연습하기 좋은 문제

https://www.acmicpc.net/workbook/view/2052

참고 자료

(C++) 순열(Permutation) 구현하기

(C++) 조합(Combination) 구현하기

[C++/Algorithm] 순열과 조합 구현하기