Next Permutation, Prev Permutation 파헤치기

1. Next Permutation 알고리즘 문제를 풀다 보면 <algorithm> 라이브러리의 next_permutation 함수를 쓸 일이 많다. 문득 이 함수의 원리가 궁금해서 이 글에 정리해보려고 한다. Next permutation의 기본 원리는 오름차순을 내림차순으로 변경하는 것이다. 변경하는 과정에서 모든 가능한 조합이 나오게 된다. 단, 수열은 사전에 오름차순 정렬되어 있어야 한다. Next_permutation의 과정을 살펴보면 아래와 같다. Next Permutation 과정 1. find max(k), a[k] < a[k+1] 2. find max(m), a[k] < a[m] && k < m 3. swap(a[k], a[m]) 4. reverse(a[k+1:]) [1, 2, 3, 4, 5]를 수동으로 한 예시다. 이런식으로 계속 반복하면..........

원문링크 : Next Permutation, Prev Permutation 파헤치기