[파이썬] Next Permutation

Next Permutation

사전순으로 다음에 올 수를 구하는 알고리즘

1 2 3 4 라는 배열이 있다고 했을때 next_permutation()을 사용하면

1 2 4 3 그러니까 사전순으로 다음 배열을 반환한다

c++에는 라이브러리로 있는데 자바에는 없어서 사용하려면 직접 구현해야한다

 

 

알고리즘 순서

1. 배열을 오름차순으로 정렬합니다

2. 뒤에서부터 탐색해 꼭대기 값을 찾습니다

3. 꼭대기-1 값보다 크거나 같은 값을 뒤에서부터 탐색해 둘을 교환합니다

4. 꼭대기값 ~ 끝값까지 오름차순 정렬합니다

5. 2~4를 반복합니다

 

이 알고리즘을 가장 잘 설명한다고 생각하는 사진을 공유한다

 

 

출처 : https://velog.io/@hongcheol/%EA%B0%9C%EB%B0%9C%EC%9D%BC%EC%A7%80210812TIL

 

 

Q. 이런거 알면 뭘 할 수 있냐?

A. dfs()보다 빠르고, 관련 알고리즘 문제를 풀 수 있다

 

 

사전순으로 다음에 오는 순열을 출력하라는 문제

N=int(input())
arr=list(map(int, input().split()))

def next_permutation():
    #꼭대기 값 찾기
    i=N-1
    while(i>0 and arr[i-1]>=arr[i]):
        i-=1

    if i==0: #내림차순 정렬 완료
        return False

    #꼭대기-1보다 큰 값 찾기
    #꼭대기+1~오른쪽 끝 값 중 큰 값이 없으면 꼭대기 값이랑 바꾼다
    j=N-1
    while(arr[i-1]>=arr[j]):
        j-=1
    arr[i-1], arr[j] = arr[j], arr[i-1]

    #꼭대기 ~ 끝까지 reverseOrder
    k=N-1
    while(i<k):
        arr[i], arr[k] = arr[k], arr[i]
        i+=1
        k-=1

    return True


if not next_permutation():
    print(-1)

else:
    for i in range(N):
        print(arr[i], end=" ")

파이썬에는 증감연산자가 없어 자바로 구현할 때에 비해 코드 길이가 늘어난다

 

문제 출처 : https://www.acmicpc.net/problem/10972

 

 

모든 순열을 출력하라는 문제

N=int(input())
arr=[]
for i in range(1, N+1):
    arr.append(i)

def next_permutation():
    #꼭대기 값 찾기
    i=N-1
    while(i>0 and arr[i-1]>=arr[i]):
        i-=1

    if i==0: #내림차순 정렬 완료
        return False

    #꼭대기-1보다 큰 값 찾기
    #꼭대기+1~오른쪽 끝 값 중 큰 값이 없으면 꼭대기 값이랑 바꾼다
    j=N-1
    while(arr[i-1]>=arr[j]):
        j-=1
    arr[i-1], arr[j] = arr[j], arr[i-1]

    #꼭대기 ~ 끝까지 reverseOrder
    k=N-1
    while(i<k):
        arr[i], arr[k] = arr[k], arr[i]
        i+=1
        k-=1

    return True


while True:
    for a in arr:
        print(a, end=" ")
    print()

    if not next_permutation():
        break

do-while이 있으면 코드길이가 줄어드는데 파이썬에는 없다

 

 

맨 위 - next_permutation 사용

중간 - permutations 라이브러리 사용

맨 아래 - dfs 사용

 

시간이 라이브러리<넥퍼<dfs 순으로 느리다. 라이브러리를 쓰자

넥퍼보단 dfs가 빠르지만 아무리 주석을 포함했다고 해도 dfs보다 코드 길이가 좀 된다

 

결론

- 순열/조합은 dfs로 풀고 넥퍼문제는 넥퍼로 풀자!

 

문제 출처 : https://www.acmicpc.net/problem/10974

 

 

주의 사항

- 조합이나 nPr을 구현하려면 추가적인 코드가 필요하다

- dfs랑 비교했을때 코드량이 많다