<algorithm> 库里有一个名不见经传的函数叫做：

简单写个用法示例：

cpp#include 
    
     #include 
     
      #include 
      
       int main(){    std::array
       
         A = {1,2,3,4};    do {        for (auto i : A)            std::cout << i << " ";        std::cout << std::endl;    } while (std::next_permutation(A.begin(), A.end()));}
       
      
     
    

输出（截取部分）：

1 2 3 4 // 2->3->4 : ascending1 2 4 31 3 2 41 3 4 21 4 2 31 4 3 2 // 4->3->2 : descending2 1 3 42 1 4 32 3 1 4

恐怕你已经发现了，这个方法可以帮助我们列出某个容器的全套排列组合。它其实还有一个兄弟函数，名曰 ，一个是向前排列，一个是向后排列，算法上大同小异。

探秘

提到这个，原因一是这对姐妹藏在深闺无人知，科普一下；更重要的原因，是我对于其排列的算法很感兴趣，它是按照什么顺序来进行排列组合的？这个 STL 算法函数如果让我来实现，会如何实现？

实际上，仔细观察上面输出，大体上我们可以看出一点端倪：

1. 总体上是从小到大。如从 1 开头，到 2 开头。
2. 当 1 开头时，将全部 1 开头的组合列完。
3. 如何保证第 2 条？发现规律是，除去开头的 1 ，剩下三个数，呈这样的规律：从递增排列到递减。
4. 第 3 条是大方向，我们再细究每一步。发现局部范围内，也是将递增变为递减，如 3,4 -> 4,3

综上，我们若要得到下一步的组合，应该将注意力集中在递增的子序列上，设置两个迭代器，start 与 last，分别指向递增子序列的手尾，用此来重点分析一下从第二行到第三行的转变。

1 2 4 3  ^ ^  s l

这种情况下， s 指向了 2，意味着 1,2 开头的组合已经排列完毕，根据第 1 条，我们希望去排列 1,3 开头的组合了。而此刻 3 在行尾，我们就希望将其提取到 2 的前头去。即变成：

1 3 2 4

果然就是咱们想要的了。可是这个插入过程实际上应分为两步：

1. swap(2, 3);
2. 4 以后的元素全部逆序

解释一下第二步，当 last 指向 4，这已经意味着 4 以后一定是降序的，即使交换了 2,3 也无法改变这个顺序。而我们所希望的，显然是保持 2,4 这样的升序，作为 1,3 开头排列的起始。所以才有了第二步的逆序。

动手

讲明算法，再来理一理实现思路。

• 首先，容器为空，或是仅有一个元素，自然返回 false。
• 然后，需要初始化 start 的位置，我们希望从后往前找，故初始状态下，指向最后一个元素。
• 最后，开始迭代过程，定位 start 与 last 的位置，详细直接见代码：

cpp#include 
    
     template
     
      bool my_next_permutation(Iterator beg, Iterator end){    if (beg == end) return false;    // 容器为空    Iterator start = end;    if (beg == --start) return false;    // 仅有一个元素    for(;;) {        Iterator last = start--;    // last 指向最后一个元素，并将 start 前移        if (*start < *last) {    // 直至定位到一个升序序列            Iterator riter = end;    // 依旧从尾部开始            while (!(*start < *--riter))    // 找到下一个排列的开头，恰是第一个大于当前开头的元素                ;            std::iter_swap(start, riter);    // 交换            std::reverse(last, end);    // 逆序            return true;        }        if (start == beg) {    // 特殊情况，即全部排列完毕(整体降序)，回到初始(整体升序)            std::reverse(beg, end);            return false;        }    }}
     
    

面试

实际上，这道题也是一道面试题，请见：

动手做做吧~