'C++' std::next_permutation

next_permutation

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last); // constexpr since C++20

template< class BidirIt, class Compare >
bool next_permutation(BidirIt first, BidirIt last, Compare comp); // constexpr since C++20

: 시퀀스를 재배열하여 다음 순열을 생성하고, 성공적으로 다음 순열을 생성하면 true를 반환합니다. 만약 현재 순열이 시퀀스에서 가능한 마지막 순열 (내림차순으로 정렬된 상태)이라면, 이 함수는 시퀀스를 첫 번째 순열 (오름차순으로 정렬된 상태)로 재배열하고 false를 반환합니다.

현재 상태에서 사전적으로 다음 순열을 찾기 때문에, 모든 순열을 빠짐없이 탐색하려면 가장 첫 번째 순열인 오름차순 정렬 상태에서 시작해야 합니다. 만약 시퀀스가 정렬되어 있지 않다면, 함수는 현재 순서에서 다음 순열을 찾지만, 가능한 모든 순열을 순회하지 못할 수 있습니다.
즉, 해당 함수를 사용하기 전에 순열을 생성하고자 하는 시퀀스를 오름차순 정렬해줘야 합니다.

(first, last]

• first : 순열을 생성할 시퀀스의 시작을 가리키는 양방향 반복자
• last : 순열을 생성할 시퀀스의 끝을 가리키는 양방향 반복자
• comp : 비교 함수 또는 함수 객체

<example> | 오름차순 정렬되지 않은 시퀀스

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

int main() {
    std::vector<int> v = { 2, 1, 3 };

    do {
        for (int i : v) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));

    return 0;
}

<결과>

<example> | 오름차순 정렬된 시퀀스

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

int main() {
    std::vector<int> v = { 1, 2, 3 };

    do {
        for (int i : v) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));

    return 0;
}

<결과>

<example> | 내림차순 정렬된 시퀀스와 순열

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

int main() {
    std::vector<int> v = { 1, 2, 3 };

    sort(v.begin(), v.end(), std::greater<int>());

    do {
        for (int i : v) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end(), std::greater<int>()));

    return 0;
}

<결과>