首页 > 代码库 > next_permitation
next_permitation
了解一个C++ STL的函数 next_permitation 可用于生成全排列
如下例子
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 using namespace std; 5 6 const int MAX_N = 128; 7 int perm[MAX_N]; 8 int POS[MAX_N]; 9 bool used[MAX_N]; 10 //dfs法求取 (0,1,2,3...n-1)的全排列 n!种 11 12 //自己定义的函数 13 void permutation1(int pos,int n) 14 { 15 if (pos == n) 16 { 17 for (int i = 0; i < n; i++) 18 { 19 printf("%d ", POS[i]); 20 } 21 putchar(‘\n‘); 22 return ; 23 } 24 for (int i = 0; i < n; i++) 25 { 26 if(!used[i]) 27 { 28 POS[pos] = i; 29 used[i] = true; 30 permutation1(pos+1, n); 31 used[i] = false;//回溯 当不用这个数的时候 取消used 32 } 33 } 34 } 35 36 //c++提供的next_permutation 37 //即使有重复元素也会排列 38 //按照字典序排列 当排序呢完后会返回false 39 void permutation2(int n) 40 { 41 for (int i = 0; i < n; i++) 42 { 43 perm[i] = i; 44 } 45 do 46 { 47 for (int i = 0; i < n; i++) 48 { 49 printf("%d ", perm[i]); 50 } 51 printf("\n"); 52 }while (next_permutation(perm, perm+n)); 53 } 54 int main() 55 { 56 int n; 57 cin >> n; 58 //permutation1(0,n);//很赞 59 permutation2(n); 60 return 0; 61 } 62 //以上属于特殊状态的枚举 又或者 可以使用位运算 枚举组合数 或者 求集合的子集 63 //以后提及
只需要打印就行了 其他的都交给permitation(perm, perm+n)
当枚举完毕 返回false
next_permitation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。