#include <algorithm>

#include <iostream>

template<typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    // 空区间
    if(first == last)
        return false;
    BidirectionalIterator i = first;
    ++i;
    // 只有一个元素
    if(i == last)
        return false;

    // i指向尾部
    i = last;
    --i;
    for (;;)
    {
        // i是j的上一个元素
        BidirectionalIterator j = i;
        --i;
        if(*i < *j)
        {
            // 由尾部往前找到第一个比*i大的元素，并交换i,k
            BidirectionalIterator k = last;
            while(!(*i < *--k))
                ;
            std::iter_swap(i, k);
            // 将[j,last)的元素逆向重排
            std::reverse(j, last);
            return true;
        }
        // 到最前面了
        if(i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}