Permutation- C++ next_permutation 사용법

Related to: Algorithm

참조

• https://en.cppreference.com/w/cpp/algorithm/next_permutation
• https://en.cppreference.com/w/cpp/algorithm/prev_permutation

Header

#include<algorithm>

Use

template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last );
 
          or
 
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

• 기본적으로 배열의 iterator를 param으로 받는다.입력 배열의 내부 원소 위치만 바꾸기(swap) 때문에 메모리가 새롭게 생성되지 않는다.
• 따라서 모든 경우의 수를 배열로 얻어야 한다면 loop 내에서 계속 호출하며 별도의 컨테이너에 복사해야 한다.
• 배열을 오름차순으로 정렬하고 사용해야 한다.변경 전 배열을 A, 변경 후 배열을 B라고 할 때 사전식(lexicographically) 순서로 비교하여 B가 A보다 크다면 true를 반환하고 그렇지 않다면 false를 반환한다.
• 리턴 값(bool)이 false라면 새로운 순열이 더 이상 없다고 간주하고 loop를 종료한다.

Example

\#include <algorithm>
\#include <string>
\#include <iostream>
 
int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}