<std::*_permutation> (std::next_permutation, std::prev_permutation)
사전 순에 따라 다음의 큰 순열로 대체할 수 있도록 범위를 재정렬 합니다. 이때 술어를 넘길 수 있는데, 술어는 이진 술어여야 합니다. 또한 배열이 정렬돼있어야 합니다. next_permutation은 first와 last 를 받아 사전순으로 재정렬 시킵니다. 만약 func 가 있다면 func를 활용합니다. 만약 교체가 성공했다면 true를, 더 이상 교체할 값이 없다면 ( 이전 순열이 다음 순열보다 사전순으로 작을때 ) false 를 리턴합니다. next_permutation 은 양방향 반복자를 받습니다. next_permutation 은 오름차순으로 정렬 된 컨테이너를 받습니다. next_permutation 은 다음과 같이 작성 돼 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | template<class BidirIt> bool next_permutation(BidirIt first, BidirIt last) { if (first == last) return false; BidirIt i = last; if (first == --i) return false; while (true) { BidirIt i1, i2; i1 = i; if (*--i < *i1) { i2 = last; while (!(*i < *--i2)) ; std::iter_swap(i, i2); std::reverse(i1, last); return true; } if (i == first) { std::reverse(first, last); return false; } } } | cs |
| vector<int> vnt = { 1,2,3 }; while (std::next_permutation(vnt.begin(), vnt.end())) { for (auto& i : vnt) cout << i << " "; cout << '\n'; } // 1 3 2 // 2 1 3 // 2 3 1 // 3 1 2 // 3 2 1 | cs |
< next_permutation 의 활용 예 >
prev_permutation 은 next_permutation 과 동일하나 역순으로 작동합니다. prev_permutation 은 양방향 반복자를 받습니다. prev_permutation 은 내림차순을 으로 정렬된 컨테이너를 받습니다. prev_permutation 은 다음과 같이 작성 돼 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | template<class BidirIt> bool prev_permutation(BidirIt first, BidirIt last) { if (first == last) return false; BidirIt i = last; if (first == --i) return false; while (1) { BidirIt i1, i2; i1 = i; if (*i1 < *--i) { i2 = last; while (!(*--i2 < *i)) ; std::iter_swap(i, i2); std::reverse(i1, last); return true; } if (i == first) { std::reverse(first, last); return false; } } } | cs |
| vector<int> vnt = { 3,2,1 }; while (std::prev_permutation(vnt.begin(), vnt.end())) { for (auto& i : vnt) cout << i << " "; cout << '\n'; } // 3 1 2 // 2 3 1 // 2 1 3 // 1 3 2 // 1 2 3 | cs |
<prev_permutation 의 활용 예>
std::*_permutation 은 중복적인 원소에 대해 지원하지 않습니다.
| vector<int> vnt = { 1,1,2 }; while (std::next_permutation(vnt.begin(), vnt.end())) { for (auto& i : vnt) cout << i << " "; cout << '\n'; } //1 2 1 //2 1 1 | cs |
<std::rotate>
std::rotate 함수는 first , middle, last 를 인자로 받으며 middle을 기준으로 회전시킵니다. ( 몇번 째 요소까지 회전시킬 지로 생각하면 쉬움 ! ) std::rotate 함수는 순방향 반복자를 입력 받습니다. std::rotate 는 다음과 같이 작성 돼 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | template<class ForwardIt> ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { if(first == n_first) return last; if(n_first == last) return first; ForwardIt read = n_first; ForwardIt write = first; ForwardIt next_read = first; // read position for when "read" hits "last" while(read != last) { if(write == next_read) next_read = read; // track where "first" went std::iter_swap(write++, read++); } // rotate the remaining sequence into place (rotate)(write, next_read, last); return write; } | cs
|
| vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; std::rotate(nvt.begin(), nvt.begin() + 1, nvt.end()); // 2,3,4,5,6,7,8,9,10,1 std::rotate(nvt.begin(), nvt.begin() + 2, nvt.end()); // 4,5,6,7,8,9,10,1,2,3 std::rotate(nvt.rbegin(), nvt.rbegin() + 2, nvt.rend()); // 2,3,4,5,6,7,8,9,10,1 std::rotate(nvt.rbegin(), nvt.rbegin() + 1, nvt.rend()); // 1,2,3,4,5,6,7,8,9,10 | cs |
< std::rotate 의 left rotate 와 right rotate >
< std::random_shuffle 과 std::shuffle >
std::random_shuffle 과 std::shuffle 은 컨테이너를 무작위 정렬 시키는데 사용되는 함수입니다. std::random_shuffle은 first와 last의 반복자만 받고 배열을 무작위 정렬시켜주긴 하나, 내부에서 rand 를 사용하고 srand을 사용하지 않기 때문에 동일한 컨테이너로 다시 디버깅하면 똑같은 값이 나타나게 됩니다. 또한 균등 분포적이지 않습니다. 이를 대체 하기 위해 의사 난수 발생기를 받는 std::shuffle 이 등장했습니다. std::random_shuffle은 C++14 부터 사용 중지 권고를 받았고, C++17에서 삭제될 예정입니다.
std::shuffle 은 컨테이너의 길이에 선형적입니다.
| vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; std::random_shuffle(nvt.begin(), nvt.end()); // 무작위 정렬이 되긴 하나, 다시 디버깅시켜도 같은 값만 나옴 | cs |
std::shuffle 은 first 와 last 그리고 의사 난수 발생기를 받습니다. std::shuffle은 임의 접근 반복자를 받습니다.
다음은 std::shuffle의 구현 내용 입니다.
| template<class RandomIt, class URBG> void shuffle(RandomIt first, RandomIt last, URBG&& g) { typedef typename std::iterator_traits<RandomIt>::difference_type diff_t; typedef std::uniform_int_distribution<diff_t> distr_t; typedef typename distr_t::param_type param_t; distr_t D; diff_t n = last - first; for (diff_t i = n-1; i > 0; --i) { using std::swap; swap(first[i], first[D(g, param_t(0, i))]); } } | cs |
| vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); auto drg = std::default_random_engine{seed}; std::shuffle(nvt.begin(), nvt.end(), drg); // 기본 랜덤 엔진(메르센 트위스터 32비트)을 쓴 첫번째 방법 std::random_device rd; std::mt19937_64 mte(rd()); std::shuffle(nvt.begin(), nvt.end(), mte); // 메르센 트위스터 64를 쓴 두번째 방법 | cs |
의사 난수 발생기에 대한 정보 : https://docs.microsoft.com/ko-kr/cpp/standard-library/random?view=vs-2017 |
