순열 (Permutation)

1. 순서가 중요한 완전 탐색에 종종 사용된다.

2. 개수가 고정된 선택 문제를 순열로 바꿔서 풀 수 있다. (조합-Combination으로 활용 가능)

(BOJ6603 로또 , https://www.acmicpc.net/problem/6603)

 

# std::next_permutation, std::prev_permutation

C++은 std::next_permutation, std::prev_permutation로 사전순(lexicographically ordered)의 다음 순열, 이전 순열을 제공한다.

 

# Time Complexity

한 번 호출하면 O(n), 모든 가능성을 전부 호출하면 Amortized O(1)

https://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation 

The amortized complexity of std::next_permutation?

 

# 예제

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// possible implementation of std::next_permutation
bool my_next_permutation(vector<int>& v)
{
    int i = v.size() - 1;
    while (i > 0 && v[i-1] >= v[i]) {
        --i;
    }
    if (i == 0) {
        return false;
    }
    
    int j = v.size() - 1;
    while (v[i-1] >= v[j]) { 
        --j;
    }
    swap(v[i-1], v[j]);

    j = v.size() - 1;
    while (i < j) {
        swap(v[i], v[j]);
        ++i; --j;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> v(N);
    for (int i = 0; i != N; ++i) {
        cin >> v[i];
    }

    //if (my_next_permutation(v)) {
    if (next_permutation(v.begin(), v.end())) { 
        for (int i = 0; i != v.size(); ++i) {
            cout << v[i] << ' ';
        }
        cout << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}

이전 순열인 prev_permutation은 다음과 같이 부호를 뒤집는 것으로 쉽게 구현할 수 있다.

bool my_prev_permutation(vector<int>& v)
{
    int i = v.size() - 1;
    while (i > 0 && v[i-1] <= v[i]) {
        --i;
    }
    if (i == 0) {
        return false;
    }
    
    int j = v.size() - 1;
    while (v[i-1] <= v[j]) { 
        --j;
    }
    swap(v[i-1], v[j]);

    j = v.size() - 1;
    while (i < j) {
        swap(v[i], v[j]);
        ++i; --j;
    }
    return true;
}

 

# Note

std::next_permutation과 std::prev_permutation은 각각 다음 순열, 이전 순열이 존재하지 않을 경우 첫 번째 순열, 마지막 순열로 컨테이너를 변환한 뒤 false를 반환한다.

 

- std::next_permutation

Transforms the range [first, last) into the next permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the first permutation (as if by std::sort(first, last)) and returns false.

- std::prev_permutation

ransforms the range [first, last) into the previous permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the last permutation (as if by std::sort(first, last); std::reverse(first, last);) and returns false.

 

https://en.cppreference.com/w/cpp/algorithm/next_permutation

std::next_permutation - cppreference.com

https://en.cppreference.com/w/cpp/algorithm/prev_permutation

std::prev_permutation - cppreference.com