从n个不同元素中任取m(m ≤ n)个元素,按照一定的顺序排列起来,叫做从 n 个不同元素中取出 m 个元素的一个排列。当m = n时所有的排列情况叫全排列。
以下举例 1,2,3,4,5 的全排列解决方案;
1.for循环解决——直接循环,保证数字不一样即可;
#include <iostream> using namespace std; void Full(int * a,int n) { for(int k1 = 0;k1 < n;k1++) { for(int k2 = 0;k2 < n;k2++) { if(k1 != k2) // ....... } } } int main() { int a[5] = {1,2,3,4,5}; Full(a,5); return 0; }
2.next_permutation()——可以查一下这个函数,下面实现全排列;
#include <iostream> #include <algorithm> using namespace std; void Full_next(int * a,int n) { sort(a,a+n); do { for(int i = 0;i < n;i++) cout << a[i] << " "; cout << endl; }while(next_permutation(a,a + n)); } int main() { int a[5] = {1,2,3,4,5}; Full_next(a,5); return 0; }
3.递归实现——加一点dfs思想,利用深度确定递归出口;
#include <iostream> using namespace std; void Swap(int & x,int & y) { int temp = x; x = y; y = temp; } void Print(int * a,int n) { for(int i = 0;i < n;i++) cout<<a[i]<<" "; cout<<endl; } void Full_dfs(int * a,int n,int i) { if(i >= n) Print(a,n); else { for(int j = i;j < n;j++) { Swap(a[i],a[j]); Full_dfs(a,n,i + 1); Swap(a[j],a[i]); } } } int main() { int a[5] = {1,2,3,4,5}; Full_dfs(a,5,0); return 0; }