枚举排列
1~n的全排列:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int a[maxn];
void print_permutation(int n,int * A,int cur){
if(cur == n){
for(int i = 0;i < n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
else{
for(int i = 1;i <= n;i++){
int ok = 1;
for(int j = 0;j < cur;j++){
if(i == A[j]) ok = 0;
}
if(ok){
A[cur] = i;
print_permutation(n,A,cur+1);
}
}
}
}
int main()
{
int n;
cin>>n;
print_permutation(n,a,0);
return 0;
}
可重集的全排列:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int b[maxn],p[maxn];
void print_set(int n,int *P,int *A,int cur){
if(cur == n){
for(int i = 0;i < n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
else{
for(int i = 0;i < n;i++){
if(!i || P[i] != P[i-1]){
int c1 = 0,c2 = 0;
for(int j = 0;j < cur;j++)
if(A[j] == P[i]) c1++;
for(int j = 0;j < n;j++)
if(P[j] == P[i]) c2++;
if(c1 < c2){
A[cur] = P[i];
print_set(n,P,A,cur+1);
}
}
}
}
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i++){
cin>>p[i];
}
print_set(n,p,b,0);
return 0;
}
解答树:
时间复杂度T(n) < n!*e = O(n!).
下一个排列:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int a[maxn],b[maxn],p[maxn];
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i++){
cin>>p[i];
}
sort(p,p+n);
do{
for(int i = 0;i < n;i++)
cout<<p[i]<<" ";
cout<<endl;
}while(next_permutation(p,p+n));
return 0;
}
上一个排列:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int a[maxn],b[maxn],p[maxn];
bool cmp(int x,int y){
return x > y;
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i++){
cin>>p[i];
}
sort(p,p+n,cmp);
do{
for(int i = 0;i < n;i++)
cout<<p[i]<<" ";
cout<<endl;
}while(prev_permutation(p,p+n));
return 0;
}