递归算法 全排序

//递归算法实现n个元素{r1,r2,…,r n}的全排列

#include

void swap(int &a,int&b)//实现两个数的交换

{

int temp;//临时变量

temp=a;

a=b;

b=temp;

}

bool isSwap(int list[],int begin,int end)//去掉重复数字的全排列。

//在交换之前先判断两个数字是否相同，不相同才交换

{

for(int i=begin;i

{

if(list[i]==list[end])

return false;

}

return true;

}

void perm(int list[],int k,int m)//实现全排列并输出

//list是待全排列的数组；k表示当前的数，m表示数组的个数

{

int i=0;

if(k==m) //一个全排列已经完成，打印整个排列

{

for(i=0;i<=m;i++)

{

printf("%d",list[i]);

}

printf("\n");

return;

}

else

{

for(i=k;i<=m;i++)//第i个数分别与它后面的数字交换就能得到新的排列

{

if(isSwap(list,k,i)) //先进行判断，不相同时才交换

{

swap(list[k],list[i]);

perm(list,k+1,m);

swap(list[k],list[i]);//上一次交换的逆交换，恢复数组

}

}

return;

}

}

int main()

{

int num;//用户自定义数组的长度num

printf("请输入数组的长度！");

scanf("%d",&num);

printf("请输入一个长度为%d的数组！",num);

int a[num];

for(int i=0;i

scanf("%d",&a[i]);

}

perm(a,0,num-1);//递归函数

return 0;

}

运行结果：