next_permutation, prev_permutation

next_permutation, prev_permutation 

c++의 레퍼런스에는 들어있지만, python에는 구현되어있지 않아 이 기회에 정리해둘겸 적어본다. 

python에는 itertools을 이용하여 순열 전체를 구하는 방법은 있다

 

기본 원리

예를 들어, [1,2,3,4]라는 것을 순열을 만든다 가정해보자

[1, 2, 3, 4]  : 오름차순 시작
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[3, 2, 4, 1]
[3, 4, 2, 1]
[4, 3, 2, 1] : 내림차순 마무리

===> 오름차순으로 시작하고, 내림차순으로 끝이 난다. 

그리고 중간에 [2,1,3,4]를 보면 특정 지점을 기준으로 오름차순, 내림차순이 이어진다. 

 

1) 배열의 뒤에서부터 오름차순이 깨지는 부분을 찾자.

예를 들어,  [1,3,4,2]가 있다고 하자

그 다음 순서를 찾기 위해서 맨 뒤에서부터 아래 조건으로 while문을 돌리자

#arr의 최대 길이 
i = len(arr) - 1

#뒤에서부터 오름차순이 깨지는 곳을 찾자..
while (i>=0 and arr[i-1] >= arr[i]): i -= 1

2) [1,3,4,2]에서 오름차순이 깨지는 부분은 [3,4]이다. 

3과 오름차순 부분[4,2]와 교체할 부분을 찾아야한다. 

j = len(arr) - 1

# arr[i-1]보다 작으면서 [4,2]에서 arr[i-1]에 가장 가까운 값을 찾자..
while(arr[i-1] >= arr[j]): j-=1

왜 가장 가까운 값을 찾느냐하면 바꿨을 때 오름차순이 유지가 되어야하기 때문이다.

둘다 찾았으면 값을 바꿔주자

arr[i-1], arr[j] = arr[j], arr[i-1]

3) 이제 [1,2,4,3]이 완성되었다.

하지만 아직 한가지 처리가 더 필요하다.  i 부터 j까지 배열을 뒤집어 줘야한다. 

 

예를 들어 [2,3,4,1]에서 2)까지 진행을 했다면 [2,1,4,3] 이다. 

여기서 [4,3]을 오름차순으로 만들어줘야지만 사전순 배치가 가능하다. 

 

while(i<j):
    arr[i], arr[j] = arr[j], arr[i]
    i+=1
    j-=1

 

전체 코드 (next_permutation)

arr = [1, 2, 3, 4]


def next_permutation():
    i = len(arr) - 1
    # 뒤에서부터 오름차순을 찾는다...오름차순이 끝나는 지점 기록
    while (i > 0 and arr[i-1] >= arr[i]):
        i -= 1
    # 0미만으로 내려가면 더이상 없다..
    if (i <= 0):
        return False

    j = len(arr) - 1

    # i위치랑 교환할 j를 찾자..
    while(arr[i-1] >= arr[j]):
        j -= 1

    arr[i-1], arr[j] = arr[j], arr[i-1]

    # 이걸 왜 해야될까???????????????
    # 사전순 배치때문에 필요한 부분이다.
    j = len(arr) -1
    while (i < j):
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

    return True


while True:
    print(arr)
    if (next_permutation()):
        continue
    break

전체 코드(prev_permutation)

arr = [9, 8, 7, 6]


def prev_permutation():
    i = len(arr) - 1

    while (i > 0 and arr[i-1] < arr[i]):
        i -= 1
    if (i <= 0):
        return False
    j = len(arr) - 1

    while (arr[i-1] <= arr[j]):
        j -= 1
    arr[i-1], arr[j] = arr[j], arr[i-1]

	j = len(arr) - 1
    while (i < j):
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1
    return True


while True:
    print(arr)
    if (prev_permutation()):
        continue
    break