[C++] Permutation

C++에서 순열을 찾기 위한 Next_permutation 및 prev_permutation은 – 헤더 파일 사용 가능

• next_permutation : 다음으로 큰 순열을 사전순으로 찾는 데 사용됩니다(123 -> 132 -> … -> 312 -> 321).
• prev_permutation: 알파벳 순서로 이전 순열을 가져오는 데 사용됩니다(321 -> 312 -> … -> 132 -> 123).

next_permutation 기본 형식

// default
template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// custom
template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

BidirectionalIterator ‘++’, ‘–‘로 도달 가능, ()로 도달 불가능(예: 목록 데이터 구조)

매개변수

• first: 시퀀스의 첫 번째 위치, 첫 번째 반복자
• last: 시퀀스의 마지막 위치, 마지막 반복자
• comp : 비교를 위해 호출 가능

돌려 주다

• bool : 다음 순열을 만들 수 있으면 true, 그렇지 않으면 false

next_permutation 예

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 3

int main()
{
    int arr(MAX);
    for (int i = 0; i < MAX; ++i) {
        arr(i) = i + 1;
    }

    do {
        for(int i = 0; i < MAX; ++i) {
            cout << arr(i) << ' ';
        }
        cout << '\n';
    } while (next_permutation(arr, arr + MAX));

    cout << "AFTER NEXT PERMUTATION" << '\n';
    for(int n : arr) {
        cout << n << ' ';
    }
    cout << '\n';

    return 0;
}

출력 결과: next_permutation 실행 후 배열이 출력되면 원래 값을 가집니다.

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
AFTER NEXT PERMUTATION
1 2 3

주의

• 오름차순으로 정렬된 경우에만 전체 순열을 찾을 수 있습니다.
  

예를 들어 배열 값이 2,3,1인 경우 next_permutation을 실행하면 다음과 같은 결과가 반환됩니다.

전체 순열을 얻으려면 정렬 후 next_permutation에 넣어야 합니다.

2 3 1 
3 1 2 
3 2 1

prev_permutation 기본 모양

// default
template <class BidirectionalIterator>
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);

//custom
template <class BidirectionalIterator, class Compare> 
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

prev_permutation 예

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 3

int main()
{
    int arr(MAX);
    for (int i = 0; i < MAX; ++i) {
        arr(i) = i + 1;
    }

    sort(arr, arr + MAX, greater<int>());
    do {
        for(int i = 0; i < MAX; ++i) {
            cout << arr(i) << ' ';
        }
        cout << '\n';
    } while (prev_permutation(arr, arr + MAX));

    cout << "AFTER NEXT PERMUTATION" << '\n';
    for(int n : arr) {
        cout << n << ' ';
    }
    cout << '\n';

    return 0;
}

출력 결과

3 2 1 
3 1 2 
2 3 1 
2 1 3 
1 3 2 
1 2 3 
AFTER NEXT PERMUTATION
3 2 1