[C++ STL] next_permutation의 내부 구현 방법

백준 문제 중 다음 순열(https://www.acmicpc.net/problem/10972) 문제를 풀던 중 생긴 의문이다.

 

dfs로 구현한 순열의 순서와 문제가 요구하는 순열의 순서가 다른 것이였다.

 

 

 

 

 

 

 

 

 

 

 

 

그래서 문제의 순서를 만족시키기 위해선 STL의 next_permutation을 사용하면 손쉽게 풀 수 있었다.

 

그럼 next_permutation은 어떤 내부 구조로 이뤄져 있을까?

 

풀 코드는 https://en.cppreference.com/w/cpp/algorithm/next_permutation에서 확인할 수 있다.

 

하지만 한 눈에 들어오지 않아 Stack Overflow의 글을 참조했다.

 

https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation의 글을 번역하면

 

예시를 들어보자.

next_permutation 과정