C++ 全排列函数 std::next_permutation与std::prev_permutation分析

无情 阅读:467 2020-10-19 15:34:56 评论:0

C++ STL中提供了std::next_permutation与std::prev_permutation可以获取数字或者是字符的全排列,其中std::next_permutation提供升序、std::prev_permutation提供降序。

1.std::next_permutation函数原型

  template <class BidirectionalIterator>

  bool next_permutation (BidirectionalIterator first, BidirectionalIterator last );

 

  template <class BidirectionalIterator, class Compare>

  bool next_permutation (BidirectionalIterator first,BidirectionalIterator last, Compare comp);

 

说明:next_permutation,重新排列范围内的元素[第一,最后一个)返回按照字典序排列的下一个值较大的组合。

返回值:如果有一个更高的排列,它重新排列元素,并返回true;如果这是不可能的(因为它已经在最大可能的排列),它按升序排列重新元素,并返回false。

2.代码实例

 1 #include <iostream> 
 2 #include <algorithm>    /// next_permutation, sort 
 3 using namespace std; 
 4 int main () { 
 5   int myints[] = {1,2,3,1}; 
 6   sort (myints,myints+4); 
 7  
 8   do { 
 9     cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << ' '<< myints[3]<<'\n'; 
10   } while ( next_permutation(myints,myints+4) );    ///获取下一个较大字典序排列 
11  
12   cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << ' '<< myints[3] <<'\n'; 
13   return 0; 
14 }

输出:

3.算法实现原理

见:http://hi.baidu.com/bellgrade/item/70b65b8a7ea3c9c398255fd4

算法描述:

1、从尾部开始往前寻找两个相邻的元素

第1个元素i,第2个元素j(从前往后数的),且i<j

2、再从尾往前找第一个大于i的元素k。将i、k对调

3、[j,last)范围的元素置逆(颠倒排列

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号