首页 > 代码库 > 7.2.1 生成1~n的排列（全排列）【STL__next_permutation()_的应用】
7.2.1 生成1~n的排列（全排列）【STL__next_permutation()_的应用】
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;int a[20];void print_permutation(int n, int a[], int cur){ int i, j; if(cur == n){ for(i = 0; i < n; ++i) printf("%d ",a[i]); printf("\n"); } else for(i = 1; i <= n; ++i){ bool flag = true; for(j = 0; j < cur; ++j) if(a[j] == i) flag = false; if(flag){ a[cur] = i; print_permutation(n, a, cur+1); } }}int main(){ print_permutation(3, a, 0); return 0;}
使用STL的next_permutation()会更加方便：
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的函数原型如下：
template<class BidirectionalIterator>bool next_permutation( BidirectionalIterator _First, BidirectionalIterator _Last);template<class BidirectionalIterator, class BinaryPredicate>bool next_permutation( BidirectionalIterator _First, BidirectionalIterator _Last, BinaryPredicate _Comp );
对于第二个重载函数的第三个参数，默认比较顺序为小于。如果找到下一个序列，则返回真，否则返回假。
所以，这道题目的代码可以这么写：
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 int main(){ 5 int n,A[100],cur=0; 6 cin >> n; 7 int i; 8 for(i=0; i<n; ++i) A[i]=i+1; 9 do{10 for(i=0; i<n; i++) cout<<A[i]<<‘ ‘;11 cout<<endl;12 }13 while(next_permutation(A,A+n));14 return 0;15 }
小结
用next_permutation和prev_permutation求排列组合很方便，但是要记得包含头文件#include <algorithm>。
虽然最后一个排列没有下一个排列，用next_permutation会返回false，但是使用了这个方法后，序列会变成字典序列的第一个，如cba变成abc。prev_permutation同理。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。