💡 퀵 접속: cpp.kr/next_permutation

next_permutation

C++ 표준 라이브러리의 알고리즘으로, 주어진 범위의 요소들을 사전식 순서로 다음 순열로 재배열합니다. 더 이상 다음 순열이 없는 경우 false를 반환합니다.

기본 사용법

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3};
    
    // 모든 순열 출력
    do {
        for (int x : v) {
            std::cout << x << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));
    
    return 0;
}

실행 결과:

커스텀 비교 함수 사용

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {3, 2, 1};
    
    // 내림차순으로 모든 순열 출력
    do {
        for (int x : v) {
            std::cout << x << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end(), std::greater<int>()));
    
    return 0;
}

실행 결과:

사용자 정의 타입에서 사용

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Person {
    std::string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 20},
        {"Bob", 25},
        {"Charlie", 30}
    };
    
    // 모든 순열 출력
    do {
        for (const auto& person : people) {
            std::cout << person.name << " (" << person.age << "세) ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(people.begin(), people.end()));
    
    return 0;
}

실행 결과:

Alice (20세) Bob (25세) Charlie (30세)
Alice (20세) Charlie (30세) Bob (25세)
Bob (25세) Alice (20세) Charlie (30세)
Bob (25세) Charlie (30세) Alice (20세)
Charlie (30세) Alice (20세) Bob (25세)
Charlie (30세) Bob (25세) Alice (20세)

참고사항

next_permutation은 algorithm 헤더에 정의되어 있습니다.
기본적으로 < 연산자를 사용하여 비교합니다.
커스텀 비교 함수를 제공할 수 있습니다.
시간 복잡도는 O(n)입니다 (n은 범위의 크기).
더 이상 다음 순열이 없는 경우 false를 반환합니다.
입력 범위는 반드시 정렬되어 있어야 합니다.
순열을 생성할 때 원본 범위를 수정합니다.

함수	설명
next_permutation(first, last)	기본 비교 연산자를 사용하여 다음 순열 구하기
next_permutation(first, last, comp)	커스텀 비교 함수를 사용하여 다음 순열 구하기