void conv(int p[],int n)
{
long m=1;
for(int i=3;i<n;)
m=m*i++;
for(int i=1;i<m;i++)
{
outp(p,n);
for(int j=n;j>1;j--)
{
swap(p[j],p[j-1]);
outp(p,n);
}
swap(p[n],p[n-1]);
outp(p,n);
for(int j=1;j<n;j++)
{
swap(p[j],p[j+1]);
outp(p,n);
}
swap(p[1],p[2]);
}
}
bool test(int p[], int n)
{
bool b=false;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(p[i]==p[j])
{
b=true;
break;
}
return b;
}
void Nnum(int p[],int n)
{
while(n>0)
{
if (test(p,n)==false) outp(p,n);
p[n]+=n-1;
for(int j=n;j>1;j--)
{
if(p[j]>n)
{
p[j]%=n;
p[j-1]+=1;
if(p[1]>n)
{
n=0;
break;
}
}
}
}
}
void recu(int p[],int n,int k)
{
if(k==n)
outp (p,n);
else
{
for(int i=k;i<=n;i++)
{
swap (p[k],p[i]);
recu(p, n,k+1);
swap (p[k],p[i]);
}
}
}
void cyc(int p[],int n,int k)
{
if (k>n)
outp(p,n);
else
{
for(int i=0;i<k;i++)
{
int t=p[1];
for(int j=2;j<=k;j++)
p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
}
}
}
void remo(int p[],int n,int k)
{
bool b;
if (k>n)
outp (p,n);
else
{
for(int i=1;i<=n;i++)
{
b=false;
p[k]=i;
for(int j=1;j<k;j++)
if(i==p[j])
{
b=true;
break;
}
if(b==false) remo(p,n,k+1);
}
}
}
int main()
{
int i,j,m;
int p[maxn];
int n;
clock_t start,finish;
cout<<"输入排列元素总数n=";
cin>>n;
for(i=1;i<=n;i++)
p[i]=i;
cout<<"1——字典序法"<<endl;
cout<<"2——递增进位数制法"<<endl;
cout<<"3——递减进位数制法"<<endl;
cout<<"4——邻位交换法"<<endl;
cout<<"5——n进制数法"<<endl;
cout<<"6——递归生成法"<<endl;
cout<<"7——循环移位法"<<endl;
cout<<"8——回溯法"<<endl;
cout<<"请选择: ";
cin>>m;
start=clock();
switch (m)
{
case 1:dict(p,n);break;
case 2:incr(p,n);break;
case 3:degr(p,n);break;
case 4:conv(p,n);break;
case 5:Nnum(p,n);break;
case 6:recu(p,n,1);break;
case 7:cyc(p,n,1);break;
case 8:remo(p,n,1);
}
finish=clock();
cout<<"程序执行时间："
<<(double)(finish-start)/CLOCKS_PER_SEC<<"秒"<<endl;
system("pause");
return 0;
}
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<time.h>
#define maxn 100
void outp(int p[],int n) //输出一个排列
{
int i;
cout<<" ";
for(i=1;i<=n;i++)
cout<<p[i]<<" ";
cout<<endl;
}
void swap(int & x,int & y)
{
int t=x;
x=y;
y=t;
}
void dict(int p[],int n) //字典序法
{
int i,j;
outp(p,n);
i=n-1;
while(i>0)
{
if (p[i]<p[i+1])
{
for(j=n;j>=i+1;j--)
if(p[i]<=p[j]) break;
swap(p[i],p[j]);
for(j=n;j>=1;j--)
{
i+=1;
if (i>=j) break;
swap(p[i],p[j]);
}
outp(p,n);
i=n;
}
i-=1;
};
}
bool midn(int m[],int n)
{
int k=n-1;
while(1)
{
m[k]+=1;
if(m[k]<n-k+1)break;
m[k]=0;
k-=1;
}
int s=0;
bool b=false;
for( k=1;k<=n;)
s+=m[k++];
if(s==0) b=true;
return b;
}
void incr(int p[],int n)
{
int m[maxn];
int i,j,a;
for(i=1;i<=n;)
m[i++]=0;
while(i>0)
{
for(i=1;i<=n;)
p[i++]=0;
for(i=1;i<=n;i++)
{
a=m[i]+1;
j=n;
while(j>0)
{
if(p[j]==0)
{
a-=1;
if(a==0) break;
}
j-=1;
}
p[j]=n-i+1;
}
outp(p,n);
if (midn(m,n)==true) break;
}
}
责任编辑：小草
您现在的位置： 
