转载自http://www.slyar.com/blog/stl_next_permutation.html
下午研究了一下全排列算法，然后发现C++的STL有一个函数可以方便地生成全排列，这就是next_permutation
在C++ Reference中查看了一下next_permutation的函数声明：
#include <algorithm>bool next_permutation( iterator start, iterator end );
The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.
从说明中可以看到 next_permutation 的返回值是布尔类型。按照提示写了一个标准C++程序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> #include <algorithm> #include <string> using namespace std ; int main ( ) { string str ; cin >> str ; sort ( str . begin ( ) , str . end ( ) ) ; cout << str << endl ; while ( next_permutation ( str . begin ( ) , str . end ( ) ) ) { cout << str << endl ; } return 0 ; }其中还用到了 sort 函数和 string.begin()、string.end() ，函数声明如下：
#include <algorithm>void sort( iterator start, iterator end );
sort函数可以使用NlogN的复杂度对参数范围内的数据进行排序。
#include <string>iterator begin();const_iterator begin() const;
#include <string>iterator end();const_iterator end() const;
string.begin()和string.end() 可以快速访问到字符串的首字符和尾字符。
在使用大数据测试的时候，发现标准C++的效率很差...换成C函数写一下，效率提升了不止一倍...
C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <cstdio> #include <algorithm> #include <cstring> #define MAX 100 using namespace std ; int main ( ) { int length ; char str [ MAX ] ; gets ( str ) ; length = strlen ( str ) ; sort ( str , str + length ) ; puts ( str ) ; while ( next_permutation ( str , str + length ) ) { puts ( str ) ; } return 0 ;