다음 순열(next permutation) 알고리즘
next permutation 은 현재 순열보다 큰 다음 순열을 찾는 알고리즘입니다.
[1, 2, 3]이 최초 숫자 배열로 주어진 경우 사전순으로 배열된 모든 가능한 순열은 아래와 같습니다.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1[1, 2, 3] = 다음으로 큰 순열은 [1, 3, 2]입니다.
[1, 3, 2] = 다음으로 큰 순열은 [2, 1, 3]입니다.
...
[3, 2, 1] = 가장 큰 순열이기 때문에 다음으로 큰 순열은 없습니다.
동작 방식
다음 순열을 얻으려면 피벗 포인트(Pivot Point)를 사용합니다.
피벗 포인트는 교환, 분할 등의 작업을 수행하기 위한 기준이 되는 위치나 값입니다.
next permutation 알고리즘에서 피벗 포인트는 순열 다음 순서를 생성하는데 필요한 요소들을 결정하는 데 사용됩니다.
next permutation에서 피벗 포인트를 사용하는 방법은 다음과 같습니다.
- 오른쪽에서 왼쪽으로 가면서, 현재 요소(i)와 바로 오른쪽 요소(i+1)를 찾습니다. i < i + 1인 경우, i가 피벗 포인트가 됩니다.
- 피벗 포인트보다 오른쪽에 위치한 요소들 중에서 피벗 포인트의 값보다 큰 가장 작은 값을 찾습니다.
- 피벗 포인트와 찾은 값을 교환(Swap)합니다.
- 피벗 포인트의 오른쪽부터 끝까지의 요소들을 오름차순으로 정렬합니다. 여기서 주목할 점은 교환 동작 후 피벗포인트의 오른쪽 요소들이 내림차순으로 정렬되어 있다는 점입니다. 따라서 그냥 이들을 뒤집으면 오름차순으로 정렬됩니다.
다음은 [2, 4, 3, 8, 5, 1] 배열에 다음 순열을 찾는 그림 예입니다.
1. 초기 순열 배열입니다.
2. 피벗 포인트를 찾는 과정입니다. 오른쪽에서 왼쪽으로 가면서 i < i+1인 피벗 포인트 i를 찾습니다.
3. 피벗 포인트의 오른쪽 요소들 중에서 피벗 포인트보다 큰 가장 작은 값을 찾습니다.
4. 피벗 포인트와 찾은 값(j)을 교환합니다.
5. 피벗 포인트의 오른쪽 요소들을 뒤집어 오름차순으로 정렬하면 다음 순열이 됩니다.
구현
알고리즘은 다음과 같습니다.
def next_permutation(arr):
# 1. 피벗 포인트 찾기(오른쪽에서 왼쪽으로 i < i + 1)
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i+1]:
i -= 1
pivot = i
# 피벗 포인트가 존재하지 않는다면(가장 큰 순열) None 리턴
if pivot < 0:
return None
# 2. 피벗 포인트보다 오른쪽에 위치한 값들 중에서 피벗 값보다 큰 가장 작은 값 찾기
j = len(arr) - 1
while j > pivot and arr[j] <= arr[pivot]:
j -= 1
# 3. 피벗 값과 찾은 값을 교환
arr[pivot], arr[j] = arr[j], arr[pivot]
# 4. 피벗 포인트 오른쪽부터 끝까지의 요소들을 오름차순으로 정렬(뒤집기)
arr[pivot + 1:] = reversed(arr[pivot + 1:])
return arr
이제 next_permutation 함수를 사용해서 [1, 2, 3]에 대한 모든 순열을 출력해 보겠습니다.
arr = [1, 2, 3]
while arr is not None:
print(arr)
arr = next_permutation(arr)
출력 결과는 다음과 같습니다.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
