순열(Permutation): C++ next_permutation 사용법

HyeongSeok Kim·2022년 8월 16일
1

Algorithm

목록 보기
2/8

참조

#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()));
}
profile
Computer Vision & SW Engineer

0개의 댓글