SLT:

 

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 #include 
     
       2 #include 
      
        3 #include 
       
         4   5 using namespace std; 6   7 int main() 8 { 9     string str;10     cin >> str;11     sort(str.begin(), str.end());12     cout << str << endl;13     while (next_permutation(str.begin(), str.end()))14     {15         cout << str << endl;16     }17     return 0;18 }
       
      
     

 

 

其中还用到了 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函数写一下，效率提升了不止一倍...

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX 100 5   6 using namespace std; 7   8 int main() 9 {10     int length;11     char str[MAX];12     gets(str);13     length = strlen(str);14     sort(str, str + length);15     puts(str);16     while (next_permutation(str, str + length))17     {18         puts(str);19     }20     return 0;21 }
       
      
     

 

 

 

 

 

转载链接:https://www.slyar.com/blog/stl_next_permutation.html