最新消息:点击查看大S的省钱秘笈

使用STL的next_permutation函数生成全排列(C++)

编程相关 Slyar 790浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

下午研究了一下全排列算法,然后发现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++程序:

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

转载请注明:Slyar Home » 使用STL的next_permutation函数生成全排列(C++)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (10)

  1. 求教, 为什么没有sort()时会有漏掉的输出?
    路旁的宁静2年前 (2014-08-06)回复
  2. 不错,确实是这样
    cchb19903年前 (2013-11-08)回复
  3. 你这个离全排列差的很远啊
    阿杜想长高4年前 (2013-06-26)回复
  4. sort也是cpp吧,STL都是c++的。说来说去就是puts比cout省很多
    logicmd4年前 (2013-01-26)回复
  5. 你一定没开 g++ -O2 优化…… 开了 O2 之后 STL 的大部分迭代器和指针等同。
    平芜泫4年前 (2012-10-14)回复
  6. C++和C在STL中速度一样
    Alchemist7年前 (2010-02-17)回复
  7. @Felix021, 恩,那本书肯定要看...我先继续肯c++ primer
    Slyar8年前 (2009-03-30)回复
  8. 鼓掌!终于开始用STL了阿~我测试了,我自己用递归写的枚举程序的效率大概是next_permutation/pre_permutation的一半~~ 推荐《STL标准模板库》,嗯。
    Felix0218年前 (2009-03-29)回复
  9. 开学了,你博客也开始写一些笔记的东东了,好怀念大学的时候。
    午夜8年前 (2009-03-28)回复