递归实现全排列.txt10有了执著，生命旅程上的寂寞可以铺成一片蓝天；有了执著，孤单可以演绎成一排鸿雁；有了执著，欢乐可以绽放成满圆的鲜花。虽说这是个蛮基础的东西
但这个鸟东西困扰了我十年了今天终于解决了～
惭愧啊实际上问题并不在于全排列问题本身
而是在于basic中的goto
当年basic中的方法是搜索回溯
十来行的代码里面三个goto搞的人团团转
最后终于彻底失去了继续参加竞赛的兴趣和动力
然后一晃就是十年
今天正在看programminginlua
又见这个鸟问题是用lua实现的递归算法
看了英文原版的书如醍醐灌顶豁然开朗
原来这么简单！
打印数组a{1,2,...,n}的全排列
递归思想：
取出数组中第一个元素放到最后，即a[1]与a[n]交换，然后递归求a[n-1]的全排列
1）如果数组只有一个元素n=1，a={1}则全排列就是{1}
2）如果数组有两个元素n=2，a={1,2}则全排列是
{2,1}--a[1]与a[2]交换。交换后求a[2-1]={2}的全排列，归结到1)
{1,2}--a[2]与a[2]交换。交换后求a[2-1]={1}的全排列，归结到1)
3）如果数组有三个元素n=3，a={1,2,3}则全排列是
{{2,3},1}--a[1]与a[3]交换。后求a[3-1]={2,3}的全排列，归结到2）
{{1,3},2)--a[2]与a[3]交换。后求a[3-1]={1,3}的全排列，归结到2）
{{1,2},3)--a[3]与a[3]交换。后求a[3-1]={1,2}的全排列，归结到2）
...
以此类推。
马上用C代码实现，成功！
#include
intg_count=1;
intg_n=0;
voidprint_result(inta)
{
inti=0;
printf("count%d:",g_count++);
for(i=0;i
{
printf("%d",a[i]);
}
printf("\n");
return;
}
#defineswap(a,b)\
{\
inttmp=a;\
a=b;\
b=tmp;\
}
voidp(inta,intsize)
{
if(size==1)
print_result(a);
else
{
inti,tmp=0;
for(i=0;i
{
swap(a[i],a[size-1]);
p(a,size-1);
swap(a[i],a[size-1]);
}
}
return;
}
voidmain(void)
{
intarray[]={1,2,3,4};
g_n=sizeof(array)/sizeof(int);
p(array,g_n);
return;
}
|
|
