Algorithms and Data Structures in Modern C++
#include <vector>
#include <algorithm>
using namespace std;
template <typename T>
bool next_permutation(vector<T>& A)
{
int k = A.size() - 1;
while (k > 0 && A[k-1] >= A[k])
--k;
if (k == 0)
return false;
swap(*find_if(A.rbegin(), A.rend(), [&](auto t){ return t > A[k-1]; }), A[k-1]);
reverse(A.begin() + k, A.end());
return true;
}
template <typename T>
bool prev_permutation(vector<T>& A)
{
int k = A.size() - 1;
while (k > 0 && A[k-1] <= A[k])
--k;
if (k == 0)
return false;
swap(*find_if(A.rbegin(), A.rend(), [&](auto t){ return t < A[k-1]; }), A[k-1]);
reverse(A.begin() + k, A.end());
return true;
}
template <typename T>
bool next_partial_permutation(vector<T>& A, int k)
{
reverse(A.begin() + k, A.end());
return next_permutation(A);
}
template <typename T>
bool prev_partial_permutation(vector<T>& A, int k)
{
bool result = prev_permutation(A);
reverse(A.begin() + k, A.end());
return result;
}
#include <algorithm>
template <typename Iterator>
bool combination(Iterator first1, Iterator last1, Iterator first2, Iterator last2, bool ASC)
{
if (first1 == last1 || first2 == last2)
return false;
Iterator m1 = last1;
Iterator m2 = last2;
--m2;
auto comp = [ASC](const auto& x, const auto& y){ return ASC ? x < y : x > y; };
while (--m1 != first1 && !comp(*m1, *m2));
bool result = m1 == first1 && !comp(*first1, *m2);
if (! result)
{
while (first2 != m2 && !comp(*m1, *first2))
++first2;
first1 = m1;
std::iter_swap(first1, first2);
++first1;
++first2;
}
if (first1 != last1 && first2 != last2)
{
m1 = last1;
m2 = first2;
while (m1 != first1 && m2 != last2)
{
std::iter_swap(--m1 , m2);
++m2;
}
std::reverse(first1, m1);
std::reverse(first1, last1);
std::reverse(m2, last2);
std::reverse(first2, last2);
}
return !result;
}
template <typename Iterator>
bool next_combination(Iterator first, Iterator middle, Iterator last)
{
return combination(first, middle, middle, last, true);
}
template <typename Iterator>
bool prev_combination(Iterator first, Iterator middle, Iterator last)
{
return combination(first, middle, middle, last, false);
}