C++ next_permutation

• C++의 라이브러리에 포함된 next_permutation 함수는 주어진 시퀀스의 다음 사전식 순열을 생성하는 데 사용됩니다.
• 이 함수는 시퀀스의 요소들을 재배열하여 사전식으로 다음 순열을 만듭니다.
• 만약 현재 순열이 마지막 순열이라면, 이 함수는 시퀀스를 첫 번째 순열(오름차순 정렬)로 재배열합니다.

반환값

다음 순열이 존재하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

동작 방식

1. 주어진 시퀀스에서 가장 긴 감소하는 후행 시퀀스를 찾습니다.
2. 그 이전의 요소를 찾아서 후행 시퀀스 내에서 이 요소보다 큰 첫 번째 요소와 교체합니다.
3. 후행 시퀀스를 오름차순으로 정렬하여 다음 순열을 만듭니다.

예제 코드

다음은 next_permutation을 사용하는 예제입니다.

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

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

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

    return 0;
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

이 예제에서는 {1, 2, 3}에 대한 모든 순열을 출력합니다. next_permutation 함수는 시퀀스를 재배열하여 사전식 순서로 다음 순열을 생성하며, 더 이상 순열이 없으면 false를 반환하여 루프를 종료합니다.

사용자 정의 비교 함수

사용자 정의 비교 함수를 사용하는 예제도 있습니다:

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

bool custom_compare(int a, int b) {
    return a > b; // 내림차순 비교
}

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

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

    return 0;
}

3 2 1 
3 1 2 
2 3 1 
2 1 3 
1 3 2 
1 2 3

위 코드에서는 내림차순으로 정렬된 시퀀스에서 내림차순 기준으로 다음 순열을 생성합니다. 사용자 정의 비교 함수 custom_compare가 사용됩니다.

추가 예제

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


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

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

    return 0;
}

1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1