【STL】next_permutation的原理和使用

1、碰到next_permutation（permutation：序列的意思）

今天在TC上碰到一道简单题（SRM531 - Division Two - Level One），是求给定数组不按升序排列的最小字典序列（Sequence of numbers A is lexicographically smaller than B if A contains a smaller number on the first position on which they differ）。

解法很简单，就是将数组排序（升序），然后从尾到头找到第一个可以交换的位置（因为可能有重复的数字）。

最后看别人的解法，排序后，用了STL中的一个函数next_permutaion，直接求到第一个不按升序排列的序列。

2、next_permutation实现原理

在《STL源码解析》中找到了这个函数，在此也简单叙述一下原理：

在STL中，除了next_permutation外，还有一个函数prev_permutation，两者都是用来计算排列组合的函数。前者是求出下一个排列组合，而后者是求出上一个排列组合。所谓“下一个”和“上一个”，书中举了一个简单的例子：对序列 {a, b, c}，每一个元素都比后面的小，按照字典序列，固定a之后，a比bc都小，c比b大，它的下一个序列即为{a, c, b}，而{a, c, b}的上一个序列即为{a, b, c}，同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，其中{a, b, c}没有上一个元素，{c, b, a}没有下一个元素。

next_permutation的函数原型如下：

Cpp代码

1 template<class BidirectionalIterator>  
 2 bool next_permutation{ 
 3       BidirectionalIterator _First,   
 4       BidirectionalIterator _Last  
 5 };  
 6 template<class BidirectionalIterator, class BinaryPredicate>  
 7 bool next_permutation{ 
 8       BidirectionalIterator _First,   
 9       BidirectionalIterator _Last,  
10       BinaryPredicate _Comp  
11  };

对于第二个重载函数的第三个参数，默认比较顺序为小于。如果找到下一个序列，则返回真，否则返回假。

函数实现原理如下：

在当前序列中，从尾端往前寻找两个相邻元素，前一个记为i，后一个记为ii，并且满足i < ii。然后再从尾端寻找另一个元素j，如果满足i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。

代码实现如下：

Cpp代码

template<class BidirectionalIterator>  
bool next_permutation(  
      BidirectionalIterator first,   
      BidirectionalIterator last  
)  
{  
    if(first == last)  
        return false; //空序列  

    BidirectionalIterator i = first;  
    ++i;  
    if(i == last)  
        return false;  //一个元素，没有下一个序列了  

    i = last;  
    --i;  

    for(;;) {  
        BidirectionalIterator ii = i;  
        --i;  
        if(*i < *ii) {  
            BidirectionalIterator j = lase;  
            while(!(*i < *--j));  

            iter_swap(i, j);  
            reverse(ii, last);  
            return true;  
        }  

        if(i == first) {  
            reverse(first, last);  //全逆向，即为最小字典序列，如cba变为abc  
            return false;  
        }  
    }  

}

prev_permutation实现类似，就是反向查找

3、使用next_permutation

思考问题，序列{a, d, c, e, b}的下一个序列是什么呢？请利用前面的分析推出答案，并用代码验证。

我这里分别用数组和vector来表示序列，用next_permutation得到下一个序列（编译环境：Dev-C++）：

Cpp代码

1 #include <cstdlib>  
 2 #include <iostream>  
 3 #include <algorithm>  
 4 #include <vector>  
 5   
 6 using namespace std;  
 7   
 8 void TestArray()   
 9 {  
10     char chs[] = {'a', 'd', 'c', 'e', 'b'};  
11     int count = sizeof(chs)/sizeof(char);  
12       
13     next_permutation(chs+0, chs + count);  
14       
15     printf("TestArray:n");  
16     for(int i = 0; i < count; i++) {  
17             printf("%ct", chs[i]);  
18     }  
19       
20     printf("n");  
21 }  
22   
23 void TestVector()  
24 {  
25      char chs[] = {'a', 'd', 'c', 'e', 'b'};  
26      int count = sizeof(chs)/sizeof(char);  
27      vector<char> vChs(chs, chs + count);  
28        
29      next_permutation(vChs.begin(), vChs.end());  
30        
31      printf("TestVector:n");  
32      vector<char>::iterator itr;  
33      for(itr = vChs.begin(); itr != vChs.end(); itr++) {  
34              printf("%ct", *itr);  
35      }  
36      printf("n");  
37 }  
38   
39 int main(int argc, char *argv[])  
40 {  
41     TestArray();  
42     printf("n");  
43     TestVector();  
44       
45     system("PAUSE");  
46     return EXIT_SUCCESS;  
47 }

运行结果：

4、小结

用next_permutation和prev_permutation求排列组合很方便，但是要记得包含头文件#include 。

虽然最后一个排列没有下一个排列，用next_permutation会返回false，但是使用了这个方法后，序列会变成字典序列的第一个，如cba变成abc。prev_permutation同理。
原文链接: https://www.cnblogs.com/cangT-Tlan/p/6055472.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍