[파이썬] Permutation 순열 나라야나 판디타 알고리즘 구현하기

Permutation(순열)

순열은 어떤 집합의 원소들을 특정한 순서로 배열하는 것을 말한다. 서로 다른 원소로 만들어진 순열의 수는 n!이다. 

ex) a, b, c가 원소일 때 순열

abc

acb

bac

bca

cab

cba

 

Compute All Permuntaion

n개의 서로 다른 문자로 만들어진 스트링이 주어졌을 떄, 이 문자열에 속하는 문자들의 모든 순열로 만들어진 n!개의 문자열을 출력하는 알고리즘을 구현해 보자.

파이썬으로 순열을 구하는 가장 기본적인 방식으로 백트래킹을 사용하는 방법이 있다. 이 방법은 문자열의 각 문자를 하나씩 고정하고, 나머지 문자를 재귀적으로 순열을 구하는 방식이다. 

 

 

def permute(str_list, start, end): 
	if start == end : 
		print("".join(str_list))
		return
	else: 
		for i in range(start, end+1):
			str_list[start], str_list[i] = str_list[i], str_list[start]
			permute(str_list, start+1, end)
			str_list[start], str_list[i] = str_list[i], str_list[start]

 

permute 함수는 문자열에서 start 인덱스부터 end 인덱스까지의 순열을 구한다. 

str_list : 문자열 list

start : 현재 고정된 문자의 인덱스 

end : 문자열의 마지막 인덱스 

 

종료조건은 start 와 end가 같을 때이다. 이 조건이 참이면, start와 end가 같아졌다는 의미로 즉, 모든 문자를 고정해서 순열을 완성한 상태가 된다. 반복문에서는 start부터 end까지 각 문자를 순서대로 고정하는 역할을 한다. 

 

 

나리야나 판디타 알고리즘 

나리야나 판디타는 14세기 인도 수학자로 모든 순열이 사전식 오름차순으로 정렬되어 있을 때 주어진 순열의 다음 순열을 찾아 주는 알고리즘을 만들었다. 

 

알고리즘 동작은 다음과 같다. 

1. 가장 큰 인덱스 K 찾기 : 배열 내에서 arr[k] < arr[k+1]을 만족하는 가장 큰 k값을 찾는다. 
2. 가장 큰 인덱스 i 찾기 :  arr[k] < arr[i]을 만족하는 가장 큰 i값을 찾는다. 
3. 값 교환 : arr[k]와  arr[i]을 교환한다. 
4. 정렬 : arr[k+1] 부터 끝까지 오름차순으로 정렬한다. 

 

1. 현재 조합에서 "변화가 일어나는" 마지막 부분을 찾아내기 위해 arr[k] < arr[k+1]을 만족하는 가장 큰 k 값을 찾는다. 예를 들어 배열기 [1, 2, 3, 4,]라고 할 때 k = 2가 된다. a[2] = 3이고 , a[3]=4로 a[2] < a[3] 조건을 만족하기 때문이다. 

 

2.  k에서 발견한 값보다 약간 더 큰 값을 찾는다. 이 값은 k 이후에 존재하는 값들 중에서 선택되어야한다. [1, 2, 3, 4]배열을 예로 들면 k=2였고, 이제 a[2] < a[i] 를 만족하는 값을 찾아야 한다. 여기서는 i = 3이 되겠다. 확인해 보면 a[3] = 4이고, a[2]=3보다 큰것을 알 수 있다.

 

3. k와 ㅑ를 찾았으면, 이 두 이ㅏㄴ덱스에 있는 값을 서로 교환한다. 이렇게 하면 배열의 사전식 배열의 사전식 순서가 유지되면서 다음 순서로 넘어갈 수 있다. 예를 들어 k = 2, i = 3에서  a[2] = 3과 a[3]=4를 교환하면 배열은 [1, 2, 4, 3]이렇게 된다.

 

4.마지막으로 k+1이후의 값들을 오름차순으로 정렬한다. 왜냐하면 이 부분의 값들이 현재 조합에서 가능한 가장 작은 순서대로 나열되어야 사전식 순서로 다음 조합이 되기 때문이다. 

 

이제  [2, 6, 5, 7, 4, 3, 1]배열을 예시로 다음에 올 순열을 찾아봐 

 

 

1. 가장 큰 인덱스 찾기 

idx 0부터 돌아가면서 idx+1과 비교한다. 

오른쪽에서 왼쪽으로 비교하면:

• a[5] = 3a와 a[6] = 1은 a[5] > a[6](조건을 만족하지 않음)
• a[4] = 4와 a[5] = 3은 a[4] > a[5] (조건을 만족하지 않음)
• a[3] = 7와 a[4] = 4는 a[3] > a[4] (조건을 만족하지 않음)
• a[2] = 5와 a[3] = 7은 a[2] < a[3] (조건을 만족!)

따라서 k = 2이다. 

 

2. 가장 큰 인덱스 i 찾기 

이제 k이후에서 a[k] < a[i]를 만족하는 가장 큰 i 를 찾아야 한다. 

a[3] = 7, a[4] = 4, a[5] = 3, a[6] = 1 중에서 a[2] = 5보다 큰 값을 찾아야 한다.

a[3]=7이 가장 크므로 i = 3이다. 

 

 

 

3. a[k]와 a[i]교환

a[2]과 a[3]의 값을 교환한다.

그러면 배열은 [2, 6, 7, 5, 4, 3, 1]가 된다. 

 

 

4. a[k+1]부터 끝까지 정렬

k+1인 2부터 끝까지 오름차순으로 정렬해주면 된다. 

[ 5, 4, 3, 1 ]을 오름차순으로 정렬하면 [1, 3, 4, 5]가 된다. 

 

그럼 [2, 6, 5, 7, 4, 3, 1] 다음에 올 순열은  [2, 6, 7, 1, 3, 4, 5]이 된다. 

 

def find_next_permutation(arr, start):
    if start == len(arr) - 1:
        return False

    # 재귀적으로 다음 순열을 찾는다.
    if find_next_permutation(arr, start + 1):
        return True
    
    # 만약 다음 순열을 찾지 못했다면, 현재 위치에서 교환을 시도한다.
    for j in range(len(arr) - 1, start, -1):
        if arr[start] < arr[j]:
            # 교환
            arr[start], arr[j] = arr[j], arr[start]
            # 그 이후의 부분을 뒤집는다.
            arr[start + 1:] = reversed(arr[start + 1:])
            return True
    
    return False

def next_permutation(arr):
    return find_next_permutation(arr, 0)

# 예시 실행
arr = [1, 2, 3]
if next_permutation(arr):
    print("다음 순열:", arr)
else:
    print("더 이상의 순열이 없음.")