티스토리 뷰
순열 알고리즘, 또는 모든 경우의 수를 계산하는 알고리즘은 개인적으로 직관적으로 생각하는 것만큼 코드로 구현하기는 쉽지 않은 알고리즘이라고 생각합니다. 먼저 순열(Permutation)은 위키피디아에서 다음과 같이 정의하고 있습니다:
수학에서, 순열(Permutation) 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값이다.
위키에서 서술했듯이, 순서 있는 n개에 대한 모든 경우의 수를 구하는 것은 n!로 굉장히 구하기 쉽습니다. 또한, 이것의 모든 경우의 수를 하나하나 나열하라고 한다고 해도, 손이 조금 아플 뿐 어려운 문제는 아닙니다. 가령, {1,2,3}이 주어졌을 때, 가능한 경우의 수는 다음과 같습니다:
- 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2
- 3 2 1
이 포스팅에서는 이것을 알고리즘으로 구현하는 방법에 대해서 살펴보겠습니다.
순열 구현(재귀)
순열을 재귀를 통해서 구현할 수 있습니다. 구글링을 했을 때, 가장 많이 보이는 알고리즘 역시 이것입니다. 아래는 이것을 C++로 구현한 코드 예시입니다 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* 순열 알고리즘 */
void Permutation(vector<int>& Array, int Start, int End)
{
if (Start == End)
{
for (const auto it : Array)
{
cout << it << " ";
}
cout << endl;
}
else
{
for (int i = Start; i <= End; ++i)
{
swap(Array[Start], Array[i]);
Permutation(Array, Start + 1, End);
swap(Array[Start], Array[i]);
}
}
}
해당 알고리즘의 수행은 다음과 같습니다:
- 인자로 배열과, 순열 알고리즘의 시작 인덱스, 순열 알고리즘의 끝 인덱스를 받습니다.
- 시작 인덱스와 끝 인덱스가 같다면, 원소가 하나이거나 모든 인덱스를 순회했다는 의미이므로 출력합니다.
- 인덱스가 서로 다르면, 시작부터 끝까지 모든 인덱스에 대해 시작 인덱스와 자리를 바꾸고 시작 인덱스를 1만큼 이동하여 재귀 함수를 호출한 후, 다시 자리를 바꾼 인덱스와 시작 인덱스의 자리를 스왑합니다. (결과적으로, dfs의 느낌을 보입니다.)
위의 재귀를 이용한 알고리즘은 그림에서 알 수 있듯이, 6가지 경우의 수를 도출하기 위해 9 * 2번의 스왑(swap)을 수행하고 있습니다.
Heap's algorithm
지루한 설명을 하자면, 힙 알고리즘은 1963년에 B.R.Heap에 의해 제안된 순열 생성 알고리즘입니다. 앞서 본 단순한 순열 알고리즘은 경우의 수에 비해 많은 스왑 연산을 요구로 하지만 힙 알고리즘의 경우, 이전 순열로부터 단일 쌍의 요소를 교환함으로써 새 경우의 수를 생성하는 방식을 통해 알고리즘의 움직임을 최소화합니다.
힙 알고리즘의 단순화한(최적은 아님) 코드 구현은 다음과 같습니다(코드 원본) :
#include <iostream>
#include <vector>
#include <algorithm>
// Generating permutation using Heap Algorithm
void HeapPermutation(vector<int>& Array, int size, int n)
{
// 사이즈가 1이면 Array를 출력합니다.
if (size == 1)
{
for(const auto it : Array)
{
cout << it << " ";
}
cout << endl;
return;
}
for (int i=0; i<size; i++)
{
// 재귀 함수 호출
HeapPermutation(Array,size-1,n);
// 사이즈가 홀수면 첫번째와 마지막을 스왑합니다.
if (size%2==1)
swap(a[0], a[size-1]);
// 사이즈가 짝수면 i번째와 마지막을 스왑합니다.
else
swap(a[i], a[size-1]);
}
}
힙 알고리즘의 원리는 코드에서도 알 수 있듯이 단순히, size가 짝수인지 홀수인지에 따라 스왑 대상이 변경된다는 것입니다. 이것에 대한 자세한 내용은 위키피디아에 기재되어 있으니, 참고하시면 될 것 같습니다. 다음 예는 위키피디아의 일부를 발췌한 것입니다:
1,2,3,4 ... Original Array
1,2,3,4 ... 1st iteration (Permute subset)
4,2,3,1 ... 1st iteration (Swap 1st element into "buffer")
4,2,3,1 ... 2nd iteration (Permute subset)
4,1,3,2 ... 2nd iteration (Swap 2nd element into "buffer")
4,1,3,2 ... 3rd iteration (Permute subset)
4,1,2,3 ... 3rd iteration (Swap 3rd element into "buffer")
4,1,2,3 ... 4th iteration (Permute subset)
4,1,2,3 ... 4th iteration (Swap 4th element into "buffer") ... The altered array is a rotated version of the original
또한 이 알고리즘은, 단순화한 코드 구현이라고 했는데, 그 이유가 스왑 동작의 최소화를 만족하지 않기 때문입니다. 위키피디아에 따르면, 재귀로 인한 콜스택을 unwind 하는 과정에서 각 레벨마다 추가적인 스왑을 야기한다고 합니다. 위 구현을 사용했을 때 swap 연산의 횟수는 다음과 같습니다:
| n | n! - 1 | swaps | additional = swaps - (n! - 1) |
| 1 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 5 | 6 | 1 |
| 4 | 23 | 27 | 4 |
| 5 | 119 | 140 | 21 |
| 6 | 719 | 845 | 126 |
| 7 | 5039 | 5922 | 883 |
| 8 | 40319 | 47383 | 7064 |
| 9 | 362879 | 426456 | 63577 |
스왑에 최적화된 코드는 다음과 같이 나타날 수 있습니다 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void HeapsAlgorithm(int Size, vector<int> Array)
{
if (Size == 1)
{
for (const auto it : Array)
{
cout << it << " ";
}
cout << endl;
return;
}
else
{
HeapsAlgorithm(Size - 1, Array);
for (int i = 0; i < Size - 1; ++i)
{
if (Size % 2 == 1)
{
swap(Array[i], Array[Size - 1]);
}
else
{
swap(Array[0], Array[Size - 1]);
}
HeapsAlgorithm(Size - 1, Array);
}
}
}
위 알고리즘은 단순히 재귀 함수가 for 반복문 시작 위치에 있던 것을 밖으로 꺼낸 것과, 뒤로 보낸 것의 차이점이 없습니다.
#include <iostream>
#include <vector>
#include <algorithm>
// Generating permutation using Heap Algorithm
void HeapPermutation(vector<int>& Array, int size, int n)
{
// 사이즈가 1이면 Array를 출력합니다.
if (size == 1)
{
for(const auto it : Array)
{
cout << it << " ";
}
cout << endl;
return;
}
for (int i=0; i<size; i++)
{
// 재귀 함수 호출
HeapPermutation(Array,size-1,n);
/* 달라지는 부분 */
if(i < size - 1)
{
// 사이즈가 홀수면 첫번째와 마지막을 스왑합니다.
if (size%2==1)
swap(a[0], a[size-1]);
// 사이즈가 짝수면 i번째와 마지막을 스왑합니다.
else
swap(a[i], a[size-1]);
}
}
}
위 알고리즘은 도중에 if문을 삽입한 것으로 최적화하였습니다. 두 경우 모두, 같은 원리에 의해 스왑이 최적화된 것으로 이것에 대한 자세한 설명은 링크된 위키피디아 문서의 Frequent Mis-implementations 섹션을 참조하시기 바랍니다.
Steinhaus–Johnson–Trotter algorithm
위키피디아에는 Steinhaus–Johnson–Trotter algorithm 알고리즘을 다음과 같이 설명하고 있습니다:
plain changes라고도 불리는 이 알고리즘은 n개의 요소에 대한 모든 순열을 생성하며, Hugo Steinhaus, Selmer M. Johnson 및 Hale F. Trotter에 의해 명명되었습니다. 순열을 생성하는 시퀀스의 각 순열은 시퀀스의 인접한 두 요소를 스왑함으로써 이전 순열과 달라집니다. 마찬가지로, 이 알고리즘은 permutohedron(육각형의 n-차원 일반화를 의미합니다.) 내의 헤밀턴 사이클에서도 찾을 수 있습니다.
단순하고 계산적으로 효율적일 뿐만 아니라, 이러한 순열이 서로 유사하기 때문에 생성된 순열에 대한 후속(subsequent) 계산이 가속화될 수 있다는 장점이 있습니다.
이 알고리즘의 구현 코드는 다음과 같습니다(원본 코드) :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool IsMobile(int, vector<int>&, vector<int>&);
// 각 요소들이 움직일 수 있는 지 검사합니다.
bool CheckMobiles(vector<int>& Array, const vector<int>& Directions)
{
for (int i = 0; i < Array.size(); ++i)
{
if (IsMobile(i, Array, Directions))
{
return true;
}
}
return false;
}
// 해당 요소가 움직일 수 있는지 검사합니다.
bool IsMobile(int p, vector<int>& Array, const vector<int>& Directions)
{
// 첫 번째 요소가 왼쪽으로 이동할 수 있다면 false입니다.
if (p == 0 && Directions[p] == 0)
{
return false;
}
// 마지막 요소가 오른쪽으로 이동할 수 있다면 false입니다.
else if (p == Array.size() - 1 && Directions[p] == 1)
{
return false;
}
else
{
// 왼쪽으로 움직일 수 있고, 왼쪽 요소보다 값이 크면 true입니다.
if (Directions[p] == 0)
{
if (Array[p] > Array[p - 1])
{
return true;
}
}
// 오른쪽으로 움직일 수 있고, 오른쪽 요소보다 값이 크면 true입니다.
else
{
if (Array[p] > Array[p + 1])
{
return true;
}
}
}
// 그 외의 경우, 전부 false입니다.
return false;
}
// 움직일 수 있는 수 중 가장 큰 수의 인덱스를 찾습니다.
int FindLargest(vector<int>& Array, const vector<int>& Directions)
{
vector<int> MobileNumbers;
// 움직일 수 있는 모든 수에 대한 인덱스를 찾습니다.
for (int i = 0; i < Array.size(); ++i)
{
if (IsMobile(i, Array, Directions))
{
// 조건을 만족하면 인덱스를 삽입합니다.
MobileNumbers.push_back(i);
}
}
int Largest = MobileNumbers[0];
// 비교 연산을 통해 움직일 수 있는 가장 큰 수의 인덱스를 찾습니다.
for (int p = 1; p < MobileNumbers.size(); ++p)
{
if (Array[MobileNumbers[p]] > Array[Largest])
{
Largest = MobileNumbers[p];
}
}
// 인덱스를 반환합니다.
return Largest;
}
// 메인 함수
void SJTAlgorithm(vector<int>& Array)
{
int k;
vector<int> Directions;
for (const auto it : Array)
{
Directions.push_back(0);
}
for (const auto it : Array)
{
cout << it << " ";
}
cout << endl;
// 배열에서 움직일 수 있는 요소가 없을 때까지 반복합니다.
while (CheckMobiles(Array, Directions))
{
// 가장 큰 수의 인덱스를 찾아서 왼쪽으로 움직일 수 있다면 스왑합니다.
k = FindLargest(Array, Directions);
if (Directions[k] == 0)
{
swap(Array[k], Array[k - 1]);
swap(Directions[k], Directions[k - 1]);
k = k - 1;
}
// 그 외의 경우, 오른쪽으로 스왑합니다.
else
{
swap(Array[k], Array[k + 1]);
swap(Directions[k], Directions[k + 1]);
k += 1;
}
for (int i = 0; i < Array.size(); ++i)
{
if (Array[i] > Array[k])
{
if (Directions[i] == 0)
{
Directions[i] = 1;
}
else
{
Directions[i] = 0;
}
}
}
for (const auto it : Array)
{
cout << it << " ";
}
cout << endl;
}
}
원본 코드는 객체 지향적으로 구성된 알고리즘이며, 위의 구현 코드는 이를 절차적 관점에서 재구성한 코드이므로, 객체 지향적 코드를 원하시는 분들은 링크를 참조하시기 바랍니다.
Steinhaus-Johnson-Trotter 알고리즘의 원리는 다음과 같습니다. 요소가 1, 2, 3, 4일 때의 예로 가정하겠습니다 :
- 오름차순으로 구성된 1,2,3,4에 대해 초기 방향을 왼쪽으로 구성합니다. 여기서 방향이란, 스왑을 할 대상에 대한 방향을 의미합니다. 이것을 시각적으로 표시하면 다음과 같습니다: <1 <2 <3 <4
- 숫자들 중에서 이동할 수 있는 가장 큰 수를 찾아서 방향에 맞게 인접한 인덱스와 스왑합니다. 여기서 "이동할 수 있는"에 대한 기준은 다음과 같습니다 :
- 숫자가 배열의 가장 왼쪽에 있으며, 방향 역시 왼쪽을 가리킨다면 이동할 수 없습니다.
- 숫자가 배열의 가장 오른쪽에 있으며, 방향 역시 오른쪽을 가리킨다면 이동할 수 없습니다.
- 위의 규칙에 의해, 4가 선정되며 방향에 의해 인접 요소 3과 자리를 바꾸며 <1 <2 <4 <3이 됩니다.
- 이후, 이동한 숫자와 배열들의 각 요소를 비교하여, 이동한 숫자보다 큰 배열 요소가 있을 때,
- 배열의 맨 왼쪽에 있던 요소이면, 방향을 오른쪽으로 변경합니다.
- 그 외의 경우 방향을 왼쪽으로 변경합니다.
- 이 규칙에 의해, <1 <2 <4 <3에서 변경되는 것은 없습니다.
위 세 가지 규칙을 앞서 사용하였던 1,2,3,4 를 예로 동작 예시를 보충하도록 하겠습니다.
- <1 <2 <3 <4
- <1 <2 <4 <3
- <1 <4 <2 <3
- <4 <1 <2 <3
- 4> <1 <3 <2 (3이 이동한 이후, 3번 규칙에 의해 4번의 방향이 바뀝니다. 이제 4는 다시 이동할 수 있습니다.)
- <1 4> <3 <2
- <1 <3 4> <2
- <1 <3 <2 4>
- <3 <1 <2 <4 (3이 이동한 이후, 3번 규칙에 의해 4번의 방향이 바뀝니다. 이제 4는 다시 이동할 수 있습니다.)
...
이런 식으로 반복하게 됩니다. 완벽해 보이는 이 알고리즘에도 단점은 있습니다. 입력되는 데이터(배열)이 반드시 오름차순으로 제공되어야 한다는 것입니다. 최악의 경우, 내림차순으로 제공하게 된다면(4 3 2 1), 4 3 2 1만을 출력하고 끝납니다. 포스팅이 길어져서, 알고리즘에 대한 설명은 여기서 마치겠습니다만 알고리즘에 대한 더 많은 정보는 위키피디아의 각각의 섹션에서 얻으실 수 있습니다.
next_permutation ( C++ )
위의 순열 알고리즘들은 최적화 여부를 떠나서 모두 성공적으로 순열의 모든 경우의 수를 출력합니다. 하지만, 위 알고리즘들을 커스터마이징해서 쓰기에는 재사용성이 높지 않습니다. 지금은 단순히 모든 경우의 수를 "출력"하는 알고리즘의 형태를 띄고 있지만, 출력이 아니라 특정한 조작을 하고 싶은 경우에는 출력하는 부분을 잘라내고, 새로이 코드를 작성해 넣어야 합니다. 이는 명백히 코드의 재사용성을 저해하는 일입니다.
C++에서는 헤더를 include하는 것으로 각각의 경우의 수에 대해서 작업 코드를 기입할 수 있는 함수를 제공하고 있습니다. 자세한 내용은 해당 링크에서 살펴볼 수 있으므로, 생략하고 사용법에 대한 예시부터 알려드리고자 합니다.
// next_permutation example
#include <iostream> // std::cout
#include <algorithm> // std::next_permutation, std::sort
int main () {
int myints[] = {1,2,3};
std::sort (myints,myints+3);
std::cout << "The 3! possible permutations with 3 elements:\n";
// next_permutation의 핵심 로직 공간
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while ( std::next_permutation(myints,myints+3) );
std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
return 0;
}
예제에서 배열 초기화 이후, 정렬하는 것을 볼 수 있는데 그 이유는 마찬가지로 오름차순이어야 next_permutation이 올바르게 작동하기 때문입니다. 그 외에는 단순하게 do - while 문 안에 원하는 로직을 삽입하면 끝입니다. 어떻게 이것이 가능한 지는 해당 블로그에서 보여주는 단순화한 구현 코드를 통해서 기초를 잡을 수 있으리라 생각합니다.
그렇다면, 각 순열마다 반환하는 것을 빼고 이 함수는 순열을 어떻게 제공할까요? next_permutation의 알고리즘의 원리는 다음과 같습니다:
- 뒤에서부터 탐색을 시작하여 오름차순의 형태를 띄는 구간이 나올 때까지 진행합니다. 이 때 작은 쪽을 i, 큰 쪽을 ii라고 하겠습니다.
- 다시 맨 뒤에서 탐색을 시작하여, i보다 큰 값이 나올 때까지 진행합니다. 멈추면, 그곳을 j라고 하겠습니다.
- i와 j를 스왑합니다.
- ii부터 마지막까지의 원소를 뒤집습니다.
1, 2, 3, 4, 5를 예시로 설명하면, 다음과 같습니다 :
- 1 2 3 4(i) 5(ii) 5에서 탐색을 시작하며 4,5가 오름차순임을 확인하고 4 위치가 i, 5 위치가 ii가 됩니다.
- 1 2 3 4(i) 5(ii)(j) 5에서 탐색을 시작하며 4보다 큰 5를 확인하고, 5 위치가 j가 됩니다.
- 1 2 3 5 4(ii) i와 j를 스왑하므로 4와 5가 바뀝니다.
- 1 2 3 5 4 ii부터 마지막 요소까지 뒤집지만 변화가 없습니다.
- 1 2 3(i) 5(ii) 4 4에서부터 탐색을 시작하여 3,5가 오름차순임을 확인하고 3 위치가 i, 5 위치가 ii가 됩니다.
- 1 2 3(i) 5(ii) 4(j) 4에서부터 탐색을 시작하여 3보다 큰 4를 확인하고, 4 위치가 j가 됩니다.
- 1 2 4 5(ii) 3 i와 j를 스왑하므로 3과 4가 바뀝니다.
- 1 2 4 3 5 ii부터 마지막 요소까지 뒤집어 3 5가 됩니다.
...
레퍼런스
순열 - 위키피디아
Steinhaus-Johnson-Trotter 알고리즘 - 위키피디아
jksk님의 티스토리 블로그 - 순열(Permutation)
Topcoder - Generationg Permutations
Google Technical Collection - Steinhaus Johnson Trotter
cplusplus - std::next_permutation
The Way - next_permutation 알고리즘
'개발 > Algorithm' 카테고리의 다른 글
| 행렬 곱셈 연산 최적화 (0) | 2019.10.22 |
|---|---|
| 소수 생성 알고리즘(Prime-generating Algorithm) (1) | 2019.09.14 |
| [C++ STL] 벡터 컨테이너(Vector) (0) | 2019.07.28 |
- Total
- Today
- Yesterday
- 구간합
- visual studio 핫 리로드
- c++ 핫 리로드
- C# 람다식
- C++
- Perforce Stream
- 알고리즘
- GoogleTest
- Perforce Streams
- P4 Streams
- 퍼포스 개요
- UE4
- game hot reload
- Visual Studio C1083
- C# lambda expression
- 퍼포스 스트림
- C7568
- DXGI
- code copyright
- MSVC C1083
- P4 Stream
- 구글테스트
- 코드 저작권
- Auto
- C++ Compile error
- c++ hot reload
- C# 익명함수
- visual studio hot reload
- 언리얼 엔진
- 행렬
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |