回溯法-全排列算法
1、常規(guī)全排列算法
#include<iostream>?
#include<algorithm>
using namespace std;?
int x[100],n,sum=0;
void backtrack(int t)
{
if(t>n) {
for(int i=1;i<=n;i++)cout<<" "<<x[i];
cout<<"\n";
sum++;
}
else{
for(int i=t;i<=n;i++){
{
swap(x[t],x[i]);
backtrack(t+1);
swap(x[t],x[i]);
}
}
? ??
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>x[i];?
cout<<"---------\n";
backtrack(1);
cout<<"---------\n";
cout<<"sum="<<sum;
return 0;
}
2、有重復(fù)元素的去重復(fù)排列算法
#include<iostream>?
#include<algorithm>
using namespace std;?
int x[100],n,sum=0;
void backtrack(int t)
{
if(t>n) {
for(int i=1;i<=n;i++)cout<<" "<<x[i];
cout<<"\n";
sum++;
}
else{
for(int i=t;i<=n;i++){
int ok=1;
for(int j=t;j<i;j++)
if(x[j]==x[i]) ok=0;
if(ok)
{
swap(x[t],x[i]);
backtrack(t+1);
swap(x[t],x[i]);
}
}
? ??
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>x[i];?
cout<<"---------\n";
backtrack(1);
cout<<"---------\n";
cout<<"sum="<<sum;
return 0;
}
3、無(wú)重復(fù)元素的去鏡像排列算法
#include<iostream>?
#include<algorithm>
using namespace std;?
int x[100],n,sum=0;
void backtrack(int t)
{
if(t==n) {
for(int i=1;i<=n;i++)cout<<" "<<x[i];
cout<<"\n";
sum++;
}
else{
for(int i=t;i<=n-1;i++){
{
swap(x[t],x[i]);
backtrack(t+1);
swap(x[t],x[i]);
}
}
? ??
}
}
void demirror()
{
for(int i=1;i<n;i++)
{
? ?swap(x[1],x[i]);
? ?for(int j=i+1;j<=n;j++)
? ?{
? ? ?swap(x[n],x[j]);
? ? ?backtrack(2);
? ? ?swap(x[n],x[j]);
? ?}
? ?swap(x[1],x[i]);
? ? }
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>x[i];?
cout<<"---------\n";
demirror();
cout<<"---------\n";
cout<<"sum="<<sum;
return 0;
}
