给出一个递归算法;
1、将一个n维数组初始化,第0位填1,第1位填2.。。。。。 第n-1位填n;
2、将数组看为两部分,一个是已排好的,剩下是待排的,分别用两个指针指向;
3、将第一个字符,依次与后n-1个字符交换值,每次交换得到一个新的首数字;
4、剩下的n-1个数字按2、3步骤重复直至所有数组完成排列;
使用c++实现,代码还有些繁琐,明天再仔细看看优化一下
1 #include<iostream>
2 using namespace std;
3
4 void swap(int *p1,int *p2)
5 {
6 //交换p1和p2指向的值
7 int tmp=*p1;
8 *p1=*p2;
9 *p2=tmp;
10 }
11 void output(int *p,int n)
12 {
13 while(n>0)
14 {
15 cout<<*p;
16 p++;
17 n--;
18 }
19 cout<<"\n";
20 }
21
22 void fill(int *p1,int *p2,int len,int n)
23 {//p1指向已填满的部分,始终指向第一个;
24 //p2指向尚余下的部 分,待插入那个;
25 //len表示已填部分的长度,n表示数组长度
26 if (len==n-1)
27 {
28 output(p1,n);//输出全部数 组
29 }
30 else
31 {
32 int *p3,*p4;
33 int *pp=(int *)malloc(n*sizeof(int));
34 for(int i=0;i<n;i++)
35 {
36 * (pp+i)=*(p1+i);
37 }
38 p3=pp;
39 while(*p3!=*p2)
40 {
41 p3++;
42 }
43 p4=p3;
44
45 for(int i=0;i<n-len;i++)
46 {
47 swap (p3,p4);
48 p4++;
49 fill (pp,p3+1,len+1,n);
50 }
51 }
52 }
53
54 void inti(int *p,int n)
55 {//将数组中所有的元素全部初始化,
56 int num=1;
57 while(num<=n)
58 {
59 *p=num++;
60 p++;
61 //cout<<num<<endl;
62 }
63 }
64
65 int main()
66 {
67 int *p,n;
68 cout<<"请输入全排列规模:";
69 cin>>n;
70 p=(int *)malloc(n*sizeof(int));
71 inti (p,n);
72 fill(p,p,0,n);
73 return 0;
74 }