[알고리즘] 백준 10974 모든 순열 / python, 순열

https://www.acmicpc.net/problem/10974

10974번: 모든 순열

 

def next_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0:
        return False
    j = n
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

a = [i+1 for i in range(int(input()))]
while True:
    print(' '.join(map(str, a)))
    if next_permutation(a) is False:
        break

이해가 안되면,, 외워야지,,

인도 수학자 나라야나 판디타가 만든 알고리즘이라고 한다

1. a[k] < a[k+1]이 성립하는 k의 최댓값을 찾는다.

2. 인덱스 k 이후의 값들중 a[k]보다 큰값의 최댓값을 찾는다.

3. a[k]와 바꾼다.

4. 인덱스 k 이후의 값들을 오름차순으로 정렬한다.

이 알고리즘을 그대로 수행하면 다음 순열이 나온다.

 

 

출처