用递归实现各种排列

为了满足字典序的输出，我采用了逐位递归的方法（每一位的所能取到的最小值都大于前一位）

1，指数型排列

#include<bits/stdc++.h>
using ll = long long int;
using namespace std;
int a[10];void printp(int m) {for (int h = 0; h <= m; h++) {if (h) cout << " ";cout << a[h];}cout << endl;return;
}void go(int i, int min, int n) {if (min > n) return;for (int k = min; k <= n; k++) {a[i] = k;printp(i);go(i + 1, k + 1, n);}return;
}int main() {int n;cin >> n;go(0, 1, n);return 0;
}

2，组合型枚举

#include<bits/stdc++.h>
using ll=long long int;
using namespace std;
int a[10];void printp(int m){for(int i=0;i<m;i++){if(i) cout<<" ";cout<<a[i];}cout<<endl;return;
}void go(int i,int min,int n,int m){if(i==m) printp(m);for(int k=min;k<=n;k++){//&&n-k>=m-1-ia[i]=k;go(i+1,k+1,n,m);}return;
}int main(){int n,m;cin>>n>>m;go(0,1,n,m);return 0;
}

 注释的部分是递归的剪枝操作，避免过早取到太大的值导致后面的值无法取，加上剪枝还是能省不少时间的

3，排列型枚举

#include<bits/stdc++.h>
using ll=long long int;
using namespace std;
int a[10],vis[10]={0};void printp(int n){for(int i=0;i<n;i++){if(i) cout<<" ";cout<<a[i];}cout<<endl;
}void go(int i,int n){if(i==n) printp(n);for(int k=1;k<=n;k++){if(vis[k]) continue;a[i]=k;vis[k]=1;go(i+1,n);vis[k]=0;}
}int main(){int n;cin>>n;go(0,n);return 0;
}

这个枚举与前两个不同，因为是排列的枚举，所以不要求字典序输出，因此问题转换成了如何避免重复，所以我专门开了一个状态数组来记录这个数位上要取的值是否已经被取过了