#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <chrono>

template<typename It>
bool next_permutation_bin(It begin, It end)
{
    if (begin == end)
        return false;
    
    It i = begin;
    ++i;
    if (i == end)
        return false;
    
    i = end;
    --i;
    
    while (true)
    {
        It j = i;
        --i;
        
        if (*i < *j)
        {
            auto test = std::lower_bound(std::make_reverse_iterator(end),
                                         std::make_reverse_iterator(i), *i);

            std::iter_swap(i, test);
            std::reverse(j, end);
            return true;
        }
        
        if (i == begin)
        {
            std::reverse(begin, end);
            return false;
        }
    }
}

template<typename It>
bool next_permutation(It begin, It end)
{
    if (begin == end)
        return false;
    
    It i = begin;
    ++i;
    if (i == end)
        return false;
    
    i = end;
    --i;
    
    while (true)
    {
        It j = i;
        --i;
        
        if (*i < *j)
        {
            It k = end;
            
            while (!(*i < *--k))
                /* pass */;
            
            iter_swap(i, k);
            reverse(j, end);
            return true;
        }
        
        if (i == begin)
        {
            reverse(begin, end);
            return false;
        }
    }
}

int bin_test(int n)
{
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 1);
    
    int count = 0;
    
    do
    {
        ++count;
    }
    while (::next_permutation_bin(v.begin(), v.end()));
    
    return count;
}

int std_test(int n)
{
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 1);
    
    int count = 0;
    
    do
    {
        ++count;
    }
    while (::next_permutation(v.begin(), v.end()));
    
    return count;
}

int main() {
    
    int count_bin = 0;
    int count_std = 0;
    
    const auto checkPoint0 = std::chrono::steady_clock::now();
    
    for (std::size_t i = 0; i < 100; i++) {
        count_bin = bin_test(10);
    }
    
    const auto checkPoint1 = std::chrono::steady_clock::now();
    const std::size_t time_bin = std::chrono::duration_cast<std::chrono::milliseconds>(checkPoint1 - checkPoint0).count();
    
    std::cout << "time in milliseconds with binary search : " <<
        time_bin << std::endl;
    
    std::cout << "number of permutations with binary search : " <<
        count_bin << std::endl;
    
    const auto checkPoint2 = std::chrono::steady_clock::now();
    
    for (std::size_t i = 0; i < 100; i++) {
        count_std = std_test(10);
    }
    
    const auto checkPoint3 = std::chrono::steady_clock::now();
    const std::size_t time_std = std::chrono::duration_cast<std::chrono::milliseconds>(checkPoint3 - checkPoint2).count();
    
    std::cout << "time in milliseconds with linear search : " <<
        time_std << std::endl;
    
    std::cout << "number of permutations with linear search : " <<
        count_std << std::endl;
    
    return 0;
}