Move Fast

순열 알고리즘 (Permutation Algorithm)

• is_permutation 두 컨테이너의 원소들이 (순서 상관없이) 일치하면 true, 그렇지 않으면 false를 반환.

  • 두번째가 첫번째의 순열이면 true.

// since C++11 until C++20
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, BinaryPredicate p );

// since C++20
template< class ForwardIt1, class ForwardIt2 >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, BinaryPredicate p );

template< class ForwardIt1, class ForwardIt2 >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, ForwardIt2 last2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, ForwardIt2 last2,
                               BinaryPredicate p );

// since C++14 until C++20
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2,
                     BinaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
using namespace std;

template<typename Os, typename V>
Os& operator<< (Os& os, V const& v) {
    os << "{ ";
    for (auto const& e : v) os << e << ' ';
    return os << "}";
}

int main() {
    static constexpr auto v1 = {1,2,3,4,5};
    static constexpr auto v2 = {3,5,4,1,2};
    static constexpr auto v3 = {3,5,4,1,1};

    cout << v2 << " is a permutation of " << v1 << ": " << boolalpha
         << is_permutation(v1.begin(), v1.end(), v2.begin()) << endl
         << v3 << " is a permutation of " << v1 << ": " << boolalpha
         << is_permutation(v1.begin(), v1.end(), v3.begin()) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
{ 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false
 */

• next_permutation 주어진 범위 내 원소들을 다음 순서로 섞은 뒤 true 반환, 다음 순서가 없으면 false 반환.

  • 사전순으로 정렬되었다고 가정하고, 다음 순서는 사전순으로 다음에 오는 것을 의미.

  • 시간 복잡도: O(N / 2), 범위의 크기 = N

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

template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

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

template< class BidirIt, class Compare >
constexpr bool next_permutation( BidirIt first, BidirIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s = "aba";
    sort(s.begin(), s.end());
    do {
        cout << s << endl;
    } while(next_permutation(s.begin(), s.end()));
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
aab
aba
baa
 */

• prev_permutation 주어진 범위 내 원소들을 이전 순서로 섞고 true 반환, 이전 순서가 없으면 false 반환.

  • 이전 순서가 없다는 것은 원소들이 사전순으로 정렬되어 있다는 의미.

  • 시간 복잡도: O(N / 2), 범위의 크기 = N

// until C++20
template< class BidirIt >
bool prev_permutation( BidirIt first, BidirIt last );

template< class BidirIt, class Compare >
bool prev_permutation( BidirIt first, BidirIt last, Compare comp );

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

template< class BidirIt, class Compare >
constexpr bool prev_permutation( BidirIt first, BidirIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s = "abcd";
    sort(s.begin(), s.end(), greater<char>());
    do {
        cout << s << endl;
    } while(prev_permutation(s.begin(), s.end()));
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
dcba
dcab
dbca
dbac
dacb
dabc
cdba
cdab
cbda
cbad
cadb
cabd
bdca
bdac
bcda
bcad
badc
bacd
adcb
adbc
acdb
acbd
abdc
abcd
 */