permutation.md

순열


nPr=n!(n−r)! ^nP_r = \frac{n!}{(n-r)!}

순열이란 n 개의 원소 중에서 r 개를 뽑아 순서를 고려하여 나열한 것이다. 위 공식은 그렇게 나열하는 경우의 수를 의미한다. {1, 2, 3} 배열에서 3개의 숫자를 순열로 뽑는다고 하면 아래와 같다.

2개의 숫자를 순열로 뽑으면 아래와 같다.


next_permutation

C++ 의 <algorithm> 헤더는 next_permutation 함수를 제공한다. 주어진 범위의 순열을 다음 사전순 순열로 바꾼다. 예를 들어 1 2 3 인 배열에 next_permutation 을 호출하면 1 3 2 가 된다.


시그니처

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

{1, 2, 3} 이 담긴 배열 array 의 전체 범위는 (array, array + 3) 으로 전달한다. last 에는 마지막 원소가 아니라 그 바로 다음 위치를 전달한다. 다음 순열이 없으면, 즉 3 2 1 처럼 내림차순인 상태에서 호출하면 배열을 오름차순 1 2 3 으로 되돌리고 false 를 반환한다. 현재 배치보다 사전순으로 앞선 순열은 나오지 않으므로, 모든 순열을 얻으려면 오름차순으로 정렬된 상태에서 시작해야 한다.


prev_permutation 은 반대로 이전 사전순 순열로 바꾼다. 모든 순열을 얻으려면 내림차순으로 정렬된 상태에서 시작해야 한다.


예시

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int array[] = {1, 2, 3};

    do
    {
        for (int i : array)
        {
            cout << i << " ";
        }
        cout << '\n';
    } while (next_permutation(array, array + 3));

}

vector 에는 begin 과 end 를 전달한다.

vector<int> vec = {1, 2, 3};
do
{
    for (int i : vec)
    {
        cout << i << " ";
    }
    cout << '\n';
} while (next_permutation(vec.begin(), vec.end()));
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

vector 를 sort 로 오름차순 정렬한 뒤, 5개 중 2개를 뽑는 순열을 출력하는 코드이다. 앞의 2개를 출력한 뒤 나머지 원소를 reverse 로 뒤집는다. next_permutation 이 바꾼 직후 뒤쪽 원소는 항상 오름차순이므로, 뒤집으면 내림차순이 되어 지금 앞 2개로 만들 수 있는 배치 중 사전순으로 가장 마지막이 된다. 따라서 다음 next_permutation 은 뒤쪽만 바꾸는 순열을 건너뛰고 앞 2개를 바꾼다. 뒤집지 않으면 1 2 가 뒤쪽 3 100 200 을 배치하는 경우의 수만큼 6 번 출력된다.

vector<int> vec = {2, 1, 3, 100, 200};

sort(vec.begin(), vec.end());

do
{
    for (int i = 0; i < 2; i++)
    {
        cout << vec[i] << " ";
    }
    cout << '\n';

    reverse(vec.begin() + 2, vec.end());
} while (next_permutation(vec.begin(), vec.end()));

구현

재귀를 이용해 순열을 직접 구현한 코드이다. 이 방식은 next_permutation 과 달리 사전순으로 출력되지 않는다. {1, 2, 3} 이면 마지막 두 줄이 3 2 1, 3 1 2 순서로 나온다.

image

위 그림은 {1, 2, 3} 에서 재귀가 갈라지는 과정이다. depth 0 에서는 첫째 칸에 올 숫자를, depth 1 에서는 둘째 칸에 올 숫자를 고른다. 파란 칸은 이미 고른 칸이라 그 아래에서는 바뀌지 않는다.


void makePermutation(int n, int r, int depth, vector<int> &vec)
{
    if (r == depth) // base case
    {
        print(vec, r);
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(vec[i], vec[depth]);
        makePermutation(n, r, depth + 1, vec); // recursion

        // swap back to restore the original order
        swap(vec[i], vec[depth]);
    }
    return;
}

전체 코드

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

void print(vector<int> &vec, int r)
{
    for (int i = 0; i < r; i++)
    {
        cout << vec[i] << " ";
    }
    cout << "\n";
}

void makePermutation(int n, int r, int depth, vector<int> &vec)
{
    if (r == depth)
    {
        print(vec, r);
        return;
    }

    for (int i = depth; i < n; i++)
    {
        cout << "[Current state : " << "i = " << i << ", depth = " << depth << "]\n";

        cout << "Swap " << i << " and " << depth << ".\n";
        swap(vec[i], vec[depth]);
        makePermutation(n, r, depth + 1, vec);

        cout << "Swap " << i << " and " << depth << " back.\n";
        swap(vec[i], vec[depth]);
    }
    return;
}

int main()
{
    vector<int> vec = {1, 2, 3};
    makePermutation(3, 3, 0, vec);

    return 0;
}
[Current state : i = 0, depth = 0]
Swap 0 and 0.
[Current state : i = 1, depth = 1]
Swap 1 and 1.
[Current state : i = 2, depth = 2]
Swap 2 and 2.
1 2 3
Swap 2 and 2 back.
Swap 1 and 1 back.
[Current state : i = 2, depth = 1]
Swap 2 and 1.
[Current state : i = 2, depth = 2]
Swap 2 and 2.
1 3 2
Swap 2 and 2 back.
Swap 2 and 1 back.
Swap 0 and 0 back.
[Current state : i = 1, depth = 0]
Swap 1 and 0.
[Current state : i = 1, depth = 1]
Swap 1 and 1.
[Current state : i = 2, depth = 2]
Swap 2 and 2.
2 1 3
Swap 2 and 2 back.
Swap 1 and 1 back.
[Current state : i = 2, depth = 1]
Swap 2 and 1.
[Current state : i = 2, depth = 2]
Swap 2 and 2.
2 3 1
Swap 2 and 2 back.
Swap 2 and 1 back.
Swap 1 and 0 back.
[Current state : i = 2, depth = 0]
Swap 2 and 0.
[Current state : i = 1, depth = 1]
Swap 1 and 1.
[Current state : i = 2, depth = 2]
Swap 2 and 2.
3 2 1
Swap 2 and 2 back.
Swap 1 and 1 back.
[Current state : i = 2, depth = 1]
Swap 2 and 1.
[Current state : i = 2, depth = 2]
Swap 2 and 2.
3 1 2
Swap 2 and 2 back.
Swap 2 and 1 back.
Swap 2 and 0 back.