[Kotlin] 순열(Permutation)
수학에서 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. n개의 원소에 대한 순열의 수는 n!(n factorial)과 같다. 조합론에서는 n개의 원소에서 k개의 원소를 배열하는 방법을 다루는 개념 등 더 많은 순열의 개념들을 사용하지만, 이번 포스트에서 다루는 순열은 n개의 원소의 순서를 섞는 n!의 경우의 수들을 구해볼 것이다.
이렇게 n개의 원소를 섞어서 나오는 모든 경우의 수를 구해서 어떤 문제를 해결한다면, 완전 탐색(Exhaustive search, Brute-force search) 방법을 이용하여 해결했다고 할 수 있다.
순열을 구하는 코드를 작성하는 알고리즘은 여러가지가 있다. 나는 크게 세 가지로 구분하여 구현했고, 세 가지 방법은 next permutation, swap & recursion, visited & recursion 이다. 그러나 세 가지 방법 모두 시간 복잡도는 O(N!)으로 나타난다. 이 시간 복잡도의 경우 원소의 개수가 많아질 수록 연산 시간은 기하 급수적으로 증가하므로 원소의 개수를 고려해서 사용해야 합니다.
- 본 포스트는 Kotlin의 문법에 대해서는 자세히 다루지 않습니다.
- 본 포스트는 Kotlin의 라이브러리에 대해서는 자세히 다루지 않습니다.
- Kotlin의 문법과 자료 구조에 대해서는 아래의 페이지를 참고 바랍니다.
Next Permutation
c++의 라이브러리에는 있지만, java와 kotlin에는 없는 함수이다. 다른 방법들과 달리 재귀적으로 사용하지 않고, 경우의 수들을 사전 순으로 나열했을 때 경우의 수들이 변하는 패턴을 이용한 방법이다.
Fig1을 보면 대략적인 흐름을 알 수 있을 것이다. 사전 순으로 경우의 수들을 나열했을 때, 규칙이 있다. 제일 처음 순서부터 예를 들어 진행해보자. 가장 뒤의 두 개의 원소들부터 위치가 바뀌고(cd -> dc), 그 후엔 끝에서 세 번째의 원소(b)도 위치가 변경된다. 끝에서 세 번째에 위치하는 원소 자리에는 사전 순으로 원래 있던 원소(b)의 다음인 원소(c)가 오며, 그 원소의 뒤는 오름차순으로 정렬(bd)된다.(acbd)
가장 끝의 세 개의 원소로 나올 수 있는 모든 경우의 수가 나오면(adcb), 다음은 가장 끝의 네 개의 원소가 서로 자리를 바꾼다(bacd). 결국 사전 순으로 마지막은 모든 원소가 내림차순으로 정렬됐을 때이다.(dcba)
이제 이 규칙을 알고리즘으로 만들어보자. 만약 n개의 원소 중에 가장 끝의 k(n>k)개의 원소가 내림차순으로 정렬되어 있다면 끝에서 k+1의 위치에 있는 원소가 바뀌어야 한다는 뜻이다. 그럼 이 원소가 어떤 원소랑 위치를 바꾸면 좋을까? 이 원소의 위치가 바뀌어야 한다는 것은 이 원소 뒤의 원소들이 내림차순으로 정렬되어 있다는 것을 뜻한다. 그리고 다음 이 자리에 와야 하는 원소는 사전 순으로 이 원소 다음인 원소이다. 그러면 끝에서 k+1의 위치에 있는 이 원소와, k 위치 이후의 원소들과 비교해서 큰(사전 순으로 뒤인) 원소 중에 가장 큰 인덱스를 얻어서 그 원소와 바꾸면 된다.
두 원소를 위치를 바꾼 후에도 여전히 k 위치 이후는 내림차순으로 정렬되어 있다. 그러나 끝에서 k+1의 위치에 다음 원소가 오면 k 위치 이후는 오름차순으로 정렬되어 있어야 한다. 따라서 k위치 이후의 원소들은 역순으로 배치하면 사전 순으로 다음 위치인 리스트를 얻을 수 있다. 이 과정의 예시를 Fig1의 가장 오른쪽에서 찾아볼 수 있다. 아래 코드는 Next Permutation 방법을 이용하여 순열을 구하는 코드이다.
Swap & Recursion
Swap & Recursion 을 이용한 방법은 원소들의 위치를 바꾸는 것과, 재귀적으로 함수를 호출하는 방식으로 모든 순열을 찾는다. 이 방식은 사전 순으로 경우의 수를 찾지 않는다. Fig2의 depth가 3인 행에서 cba, cab를 보면 사전 순이 아님을 알 수 있다. 또 이 방식은 back tracking 기법을 이용한다. Back tracking은 재귀 함수의 리턴 이후 재귀 호출을 하기 전의 어떤 상태로 되돌리는 것이 특징이다.
Visited & Recursion
Boolean visited 배열 & Recursion을 이용한 방법 역시 Back tracking 기법을 이용한다. Swap 방식과는 다르게 입력 받은 List가 오름차순 정렬되어 있다면 사전 순으로 경우의 수들을 구할 수 있다.
Fig3–2는 Boolean을 담는 것이 아닌 원소를 담는 visited, unvisited 두 개의 리스트와 Recursion을 이용하여 순열을 구하는 과정을 나타냈다. Kotlin에서는 flatMap이라는 함수를 재귀 함수와 함께 이용하여 좀 더 간단하게 나타낼 수 있다.
지금까지 Kotlin으로 모든 순열을 구하는 방법들을 알아보았다. 시간 복잡도는 각 방법이 비슷하기 때문에, 각자에게 편한 방법과 사전 순서, 혹은 과정의 값이 필요한 경우를 고려하여 사용하면 될 것 같다.
Reference
- [위키백과] “순열” — https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4
2. [뱀귤 블로그] “순열 Permutation (Java)” — https://bcp0109.tistory.com/14
