全排列和next_permutation与prev_permutaion的源码分析

全排列定义：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列

一个简单的例子就是三个数123的全排列结果是

123,132,213,231,312,321

next_permutation函数功能是生成当前排列的下一个排列，如123->132

其功能也可以看成是另一个问题，如何交换当前排列的元素顺序使得排列后的元素值上升最小。

例如123的下一个排列是132，其他任何排列值other相比132,都存在abs(other-123) > abs(132-123).

首要问题可以看成是，首先找到哪一位能提升且提升最小。

假设有一个从右往左看的升序序列

9，8，7，6，5，4，3，2，1

其中任意两位数交换都会导致 高位数字降低 和 低位数字升高，低位的升高对于整体的提升不如高位降低带来的影响大，反应在整体上的表现就是整体值的降低。

所以能得出一个结论：

从右往左看的升序序列中不存在能交换的元素使得整体值提高。

那么来看一下从右往左看的降序序列

1，2，3，4，5，6，7，8，9

对于从右往左看的降序序列，其中任意两位数交换都会导致 高位数字升高 和 低位数字降低，低位的降低对于整体的下降不如高位升高带来的提升的影响大，反应在整体上的表现就是整体值的升高。

所以能得出一个结论：

从右往左看的降序序列中任意交换的两个元素都能使得整体值提高。

那么问题转化为该选择哪一个高位和低位的来进行交换使得提升最小？

高位越往右其权重就越低，那么该位的提升对于整体的影响就越小，综合前面的结论

从右往左看的升序序列中不存在能交换的元素使得整体值提高。

就可以从右往左找到第一个降序的两个元素，即 a[i] < a[i+1] ，其中a[i]就是能够提升的高位。

记住next_permutation的一个功能是提升，所以a[i]需要从它的右边的元素中找到交换后能使得它提升是最小的一个元素。即右边元素中第一个大于它的元素，设为a[j]

那么找到符合这个条件的a[j]后，交换a[j] 和a[i]。

同时次数的元素高位i的位置上升了，但其右边还是升序的，需要倒转一下才能保证整体的提升最小。

综合以上分析，next_permutaion的整体步骤如下：

从右往左找到第一个降序序列,a[i] < a[i+1]
从右往左找到第一个满足a[j]>a[i]的元素
交换a[i] a[j]
倒转a[i]之后的所有元素

prev_permutaion的目的与next_permutaion相反，但整体上与之类似。

prev_permutaion的问题如何交换当前排列的元素顺序使得排列后的元素值下降最小。

首要问题是：首先找到哪一位能下降且下降最小。

还以之前的例子来看：

从右往左看的降序序列

1，2，3，4，5，6，7，8，9

之前得出一个结论：

从右往左看的降序序列中任意交换的两个元素都能使得整体值提高。

其也就是说

从右往左看的降序序列中不存在能交换的元素使得整体值降低。

那么prev_permutaion第一步中就是从右往左找第一个升序。

找到能一个升序位置a[i], 满足a[i] > a[i+1]时，就要从右边的元素中找到能使得它降低值最小的。

第二步就是从右往左找到第一个 a[j] < a[i]的元素。

后面与next_permutaion相同，交换a[i] 和a[j]后倒转之后的所有元素。

来看下stl里的next_permutaion的源码。

_EXPORT_STD template <class _BidIt>
_CONSTEXPR20 bool next_permutation(_BidIt _First, _BidIt _Last) {
    // permute and test for pure ascending
    return _STD next_permutation(_First, _Last, less<>{});
}

只传入了两个参数的函数进行转法，前面两个参数一样，后面增加了less类作为比较函数。

再次深入

 _EXPORT_STD template <class _BidIt, class _Pr> 
_CONSTEXPR20 bool next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred) { 
    // permute and test for pure ascending 
    _Adl_verify_range(_First, _Last); 
    auto _UFirst      = _Get_unwrapped(_First); 
    const auto _ULast = _Get_unwrapped(_Last); 
    auto _UNext       = _ULast; 
    if (_UFirst == _ULast || _UFirst == --_UNext) { 
        return false; 
    } 
    for (;;) { // find rightmost element smaller than successor 
        auto _UNext1 = _UNext; 
        if (_DEBUG_LT_PRED(_Pred, *--_UNext, *_UNext1)) { // swap with rightmost element that's smaller, flip suffix 
            auto _UMid = _ULast; 
            do { 
                --_UMid; 
            } while (!_DEBUG_LT_PRED(_Pred, *_UNext, *_UMid)); 

            swap(*_UNext, *_UMid); // intentional ADL 
            _STD reverse(_UNext1, _ULast); 
            return true; 
        } 
        if (_UNext == _UFirst) { // pure descending, flip all 
            _STD reverse(_UFirst, _ULast); 
            return false; 
        } 
    } 
}

去除掉一些包装，整体代码等价如下：

  template <class _BidIt, class _Pr> 
 bool next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred) { 
     
    auto _UFirst = _First; 
    auto _ULast = _Last; 
    auto _UNext = _ULast;
    //1个以下就没东西可以排列 
    if (_UFirst == _ULast || _UFirst == --_UNext) { 
        return false; 
    } 
    for (;;) { // find rightmost element smaller than successor 
        auto _UNext1 = _UNext;//Unext是右边的迭代器指针， 
        if (*--_UNext < *_UNext1) { //这迭代器指针向左移动，顺便进行比较，找到一个升序
            auto _UMid = _ULast;
            //这个从右到左循环找到 第一个大于*_UNext的元素，进入这里时,_UNext已经是前面说的是a[i]的i了
            //这里开始找j,也就是_UMid
            do { 
                --_UMid; 
            } while (!(*_UNext < *_UMid)); 

            swap(*_UNext, *_UMid); // 等价于交换a[i] a[j]
            reverse(_UNext1, _ULast);// 把a[i]后面的所有元素倒转
            return true; 
        } 
        if (_UNext == _UFirst) { // 如果没有升序就，倒转并返回false，说明全排列已经结束 
            reverse(_UFirst, _ULast); 
            return false; 
        }         
    } 
}

再来看下prev_permutaion

_EXPORT_STD template <class _BidIt>
_CONSTEXPR20 bool prev_permutation(_BidIt _First, _BidIt _Last) {
    // reverse permute and test for pure descending
    return _STD prev_permutation(_First, _Last, less<>{});//仍然是转发，比较还是用的less
}

继续深入

_EXPORT_STD template <class _BidIt, class _Pr>
_CONSTEXPR20 bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred) {
    // reverse permute and test for pure descending
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    auto _UNext       = _ULast;
    if (_UFirst == _ULast || _UFirst == --_UNext) {
        return false;
    }

    for (;;) { // find rightmost element not smaller than successor
        auto _UNext1 = _UNext;
        if (_DEBUG_LT_PRED(_Pred, *_UNext1, *--_UNext)) { // swap with rightmost element that's not smaller, flip suffix
            auto _UMid = _ULast;
            do {
                --_UMid;
            } while (!_DEBUG_LT_PRED(_Pred, *_UMid, *_UNext));

            swap(*_UNext, *_UMid); // intentional ADL
            _STD reverse(_UNext1, _ULast);
            return true;
        }

        if (_UNext == _UFirst) { // pure ascending, flip all
            _STD reverse(_UFirst, _ULast);
            return false;
        }
    }
}

去除掉一些包装，整体代码等价如下：

template <class _BidIt, class _Pr>
bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred) {
    
    auto _UFirst = _First;
    auto _ULast = _Last;
    auto _UNext = _ULast;
    if (_UFirst == _ULast || _UFirst == --_UNext) {
        return false;
    }

    for (;;) { 
        auto _UNext1 = _UNext;
        if ( *_UNext1 < *--_UNext)) {//这里就是与next_permutaion的*--_UNext < *_UNext1的不同,交换了顺序，也就是等同于找第一个升序
            auto _UMid = _ULast;
            do {
                --_UMid;
            } while (!( *_UMid < *_UNext));//next_permutaion是!(*_UNext < *_UMid), 也通用是顺序变了，也就是找一个下余a[i]的

            swap(*_UNext, *_UMid); 
            reverse(_UNext1, _ULast);
            return true;
        }

        if (_UNext == _UFirst) {
            reverse(_UFirst, _ULast);
            return false;
        }
    }
}

全排列和next_permutation与prev_permutaion的源码分析

作者