// <algorithm> 
// 默认(1)
template <class BidirectionalIterator>
    bool next_permutation (
        BidirectionalIterator first,
        BidirectionalIterator last);
// 自定义(2)    
template <class BidirectionalIterator,
    class Compare>
    bool next_permutation (
        BidirectionalIterator first,
        BidirectionalIterator last,
        Compare comp);

返回给定范围中的元素组成的下一个按字典序的排列。

该函数等价于:

template<class _BidIt,
class _Pr> inline
    bool _Next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
{	// permute and test for pure ascending, using _Pred
    _BidIt _Next = _Last;
    if (_First == _Last || _First == --_Next)
        return (false);

    for (;;)
    {	// find rightmost element smaller than successor
        _BidIt _Next1 = _Next;
        if (_DEBUG_LT_PRED(_Pred, *--_Next, *_Next1))
        {	// swap with rightmost element that's smaller, flip suffix
            _BidIt _Mid = _Last;
            for (; !_DEBUG_LT_PRED(_Pred, *_Next, *--_Mid);)
                ;
            _STD iter_swap(_Next, _Mid);
            _STD reverse(_Next1, _Last);
            return (true);
        }

        if (_Next == _First)
        {	// pure descending, flip all
            _STD reverse(_First, _Last);
            return (false);
        }
    }
}
  • firstlast

    分别指向序列中初始及末尾位置的双向迭代器(Bidirectional Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    comp

    二元谓词(Binary)函数,以范围中的两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 如果能重排生成更大的字典序(Lexicographically)排列,则返回 true

    否则,返回 false

  • 参照 std::sort 以获得与自定义函数谓词、函数对象谓词、对象数组、lambda 表达式 C++11、初始化列表 std::initializer_list C++11 等相关的例子。

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    
    namespace ClassFoo{
        void NextPermutation_1() {
            std::vector<int> foo;
            foo.push_back(4);
            foo.push_back(5);
            foo.push_back(6);
            do{
                // 打印 foo
                std::copy(
                    foo.begin(),
                    foo.end(),
                    std::ostream_iterator<int>(std::cout, " "));
                std::cout << std::endl;
            } /* 返回下一组排列 */
            while (std::next_permutation(foo.begin(), foo.end()));
        }
    }
    int main()
    {
        ClassFoo::NextPermutation_1();
        return 0;
    }

    4 5 6
    4 6 5
    5 4 6
    5 6 4
    6 4 5
    6 5 4 

  • 复杂度

    O(N/2)N 等值于 std::distance(first,last)

    数据争用相关

    修改在范围 [first,last) 中的元素。

    异常安全性相关

    如果元素交换(Swap)、或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)