permutation.md
순열
순열이란 n 개의 원소 중에서 r 개를 뽑아 순서를 고려하여 나열한 것이다. 위 공식은 그렇게 나열하는 경우의 수를 의미한다. {1, 2, 3} 배열에서 3개의 숫자를 순열로 뽑는다고 하면 아래와 같다.
- 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2
- 3 2 1
2개의 숫자를 순열로 뽑으면 아래와 같다.
- 1 2
- 2 1
- 1 3
- 3 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);
- first : 범위의 첫 원소를 가리키는 반복자.
- last : 범위의 마지막 원소 바로 다음 위치를 가리키는 반복자.
- 반환값 : 다음 순열로 바꿨으면
true, 다음 순열이 없으면false.
{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 순서로 나온다.
위 그림은 {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.