无聊就进来看看：关于排列数字的所有可能组合

fansfamily

因为需要写一个排列数字的所有可能组合，于是我开始思考：

比如给出1至4四个数字

int iTable[4] = {1,2,3,4};

那么写出他们的所有可能的组合为：

4 3 2 1        4 3 1 2        4 2 3 1        4 2 1 3        4 1 3 2        4 1 2 3        3 4 2 1        3 4 1 2
3 2 4 1        3 2 1 4        3 1 4 2        3 1 2 4        2 4 3 1        2 4 1 3        2 3 4 1        2 3 1 4
2 1 4 3        2 1 3 4        1 4 3 2        1 4 2 3        1 3 4 2        1 3 2 4        1 2 4 3        1 2 3 4

共4*3*2*1=24组，看来是个阶乘，那么是不是可以for (int i=0;i<24;i++)?

显然不可以。那么写个阶乘的递归吧！可是….可是…..努力了半天之后发现我做不到！！！

哪位大大可以帮帮忙把它写出来让我看看啊？？？

我得想想其他办法！于是我想到了寻路问题，好像叫图…翻了一下书，嗯！确实有这么一种。又半天时间，终于搞定了，但是…

排列出来的数字好像不怎么”规矩”……

再经过整整一整天的努力，呼~~~~~~~
搞定了，世界清净了。

我高兴得像个孩子般乱跳，可跳完之后我又不高兴了：“整整两天啊！！！！我适合做这行吗？？？”
谁能告诉我？？？我需要别人的意见！！！

我发现递归虽然很有用，但不好理解(当然也就不容易用)，特别是和循环在一起的时候，谁能说一说用的时候要从哪下手？有什么技巧？

呵呵，罗嗦了这么多，大家练练手吧！排列数字的所有可能组合
要有人感兴趣，过两天我把我的贴出来！没人感兴趣？那算了。

另：财产已冻结兄弟的"算大数（比如100）阶乘的思路"有时间我会仔细看看的。

daviescai

《数据结构、算法与应用》中有个递归的实现方法例子

mik

原帖由 fansfamily 于 2006-1-5 12:44 发表
因为需要写一个排列数字的所有可能组合，于是我开始思考：

比如给出1至4四个数字

int iTable[4] = {1,2,3,4};

那么写出他们的所有可能的组合为：

4 3 2 1        4 3 1 2        4 2 3 1        4 2 1 3        4 1 3 2        4 1 2 3        3 ...

打印出所有4位数的组合,然后去除掉了所有相同数字的组合.

RobinHoo

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <alloc.h>
   
5. int UpLimit;
   
6. int *Array;
   
7. int checkArray();
   
8. void printArray();
   
9. main()
   
10. {
    
11.         int i,Index;
    
12.         printf("Please let me know the N:");
    
13.         scanf("%d",&UpLimit);
    
14.         Array=(int *) calloc(UpLimit,sizeof(int));
    
15.         for (i=1;i<UpLimit;i++) Array[i]=0;
    
16.         while (Array[UpLimit-1]<=UpLimit)
    
17.         {
    
18.                 Array[0]++;
    
19.                 if (Array[0]<=UpLimit)
    
20.                 {
    
21.                         if (checkArray()) printArray();
    
22.                         continue;
    
23.                 }
    
24.                 Array[0]=0;
    
25.                 Index=1;
    
26.                 while (Index<UpLimit)
    
27.                 {
    
28.                         Array[Index]++;
    
29.                         if (Array[Index]<UpLimit+1) break;
    
30.                         Array[Index]=0;
    
31.                         Index++;
    
32.                 }
    
33.                 if (Index>=UpLimit) break;
    
34.         }
    
35.         free(Array);
    
36.         return 0;
    
37. }
    
38. 
    
39. int checkArray()
    
40. {
    
41.         int i,j;
    
42.         for (i=0;i<UpLimit-1;i++)
    
43.         {
    
44.                 if (Array[i]==0) return 0;
    
45.                 for (j=i+1;j<UpLimit;j++) if (Array[i]==Array[j] || Array[j]==0) return 0;
    
46.         }
    
47.         return 1;
    
48. }
    
49. 
    
50. void printArray()
    
51. {
    
52.         int i;
    
53.         for(i=0;i<UpLimit;i++) printf("%3d ",Array[i]);
    
54.         printf("\n");
    
55. }
    

复制代码

zhhui2000

写了个最简思维的．

1. print_it()
   
2. {
   
3.         char sNum[5];
   
4.         int i,j,k,l;
   
5.         for(i=1;i<5;i++)
   
6.         {
   
7.                 for(j=1;j<5;j++)
   
8.                 {
   
9.                         if (j==i) continue;
   
10.                         for(k=1;k<5;k++)
    
11.                         {
    
12.                                 if (k==j || k==i) continue;
    
13.                                 for(l=1;l<5;l++)
    
14.                                 {
    
15.                                         if (l==k ||l==j ||l==i) continue;
    
16.                                         printf("%d%d%d%d\n",i,j,k,l);
    
17.                                 }
    
18.                         }
    
19.                 }
    
20.         }
    
21. }

复制代码

[ 本帖最后由 zhhui2000 于 2006-1-5 19:51 编辑 ]

win_hate

http://www.cublog.cn/u/20/?u=htt ... howart.php?id=58123

fansfamily

首先谢谢所有回帖的朋友！谢谢！！！

2楼－daviescai：

不管如何，谢谢！

《数据结构、算法与应用》中有个递归的实现方法例子

是否就是排列数字的所有可能组合？

如果只是单纯的递归例子――我想可能是我的语言表达有问题，我并不是不会用递归，只是我在解这道题时，像五楼的答案，我想把它以递归的形式实现，以便能接收任意多个数字。但是该怎样实现？从哪入手？我不知道！因此寻求别人的帮助。

3楼－mik

我并没有丝毫对你有意见的意思，但是――想的比说的容易，说的比做的简单。

即使打印出所有N位数的组合，但去除掉了所有相同数字的组合是很费时的，同意吗？

4楼－RobinHoo：

果然是骑士！我很佩服你，这么短的时间内就找到办法解决了问题。

你的实现我仔细看了，是通过不断比较，不断进位达到目的的！这确是一种很好的思路。看得出是你自己想出来的。向你致敬！

不足的是每次都要查找比较，且进位慢（要等前面所有位填充满），所以也比较费时，相信你也察觉到了。
我找了个大于10的数字试试^_^：！把我的CPU累个半死！且排列出的数字不”规矩”。

建议看看六楼win_hate ( @v@)的方案。

同时想问一下，你运行的环境是什么？恐怕不是window吧！我用的是VS.net，可是编译时提示找不到alloc.h，找到了也有一大堆问题，改用WinGW也一样。

五楼－zhhui2000：

我只能说确实是最简单的思维：！人为干预的痕迹太重了，如果我想排列10个数字的所有组合呢？呵呵~~~让你费心了，试试能否把它用递归的形式实现。

六楼－win_hate ( @v@)：

不愧为版主，原来这题早有人研究过了！
不过两个方案中都有个明显的问题：(2) 假定 1, 2, ..., k 的 k! 个排列 P(k) 已经给定，考虑 P(k+1).如果我想排列10个数字的所有组合，那么首先要把前面九个全部排列出来……并且排列出的数字不”规矩”。

不得不承认，两种方案都是很巧妙的方法，有些异曲同工。想出方案的人肯定对这很有研究。在下对此佩服得五体投地，自愧不如！

接下来是我的实现结果。

fansfamily

1. 
   
2. void run_sort(int inow,int icount,int isize)
   
3. {
   
4.         int iTemp = isize - inow;
   
5.         if (icount < inow)
   
6.         {
   
7.                 int iValue = iTable[iTemp + icount];
   
8.         //        if (iValue == iTable[iTemp] && iTemp + icount + 1 < isize)
   
9.                 if (icount != 0 | inow == 1)
   
10.                 {
    
11.                         for (int i=0;i<iTemp;i++)
    
12.                         {
    
13.                                 cout<<iTable[i];
    
14.                         }
    
15.                         cout<<iValue;
    
16.                         for (int i=iTemp;i<isize;i++)
    
17.                         {
    
18.                                 if (iTable[i] != iValue)
    
19.                                 {
    
20.                                         cout<<iTable[i];
    
21.                                 }
    
22.                         }
    
23.                         cout<<"\t";
    
24.                 }
    
25.                 icount++;
    
26.         }
    
27.         if (icount >= inow)
    
28.         {
    
29.                 icount = 0;
    
30.                 inow++;
    
31.         }
    
32.         iTemp = isize - inow;
    
33.         if (inow < isize)
    
34.         {
    
35.                 run_sort(inow,icount,isize);
    
36.         }
    
37. }
    

复制代码

思路是通过替换每位数，后来搞混了，有些乱七八糟了。

fansfamily

好像还有个名堂，叫深度（还是广度？）优先搜索。

1. 
   
2. #include <fstream>
   
3. #include <iostream>
   
4. #include <time.h>
   
5. using namespace std;
   
6. int **imap;
   
7. int *path;
   
8. bool *bselected;                //当前数字是否已排上
   
9. int *iTable;
   
10. int iselected = 0,ibeg = 0,iend = 0,isize = 0;
    
11. void Init_Table(int isize)
    
12. {
    
13.         iTable = new int[isize];
    
14.         for (int i=0;i<isize;i++)
    
15.         {
    
16.                 iTable[i] = i+1;
    
17.         }
    
18. }
    
19. void Init_Map(int isize)
    
20. {
    
21.         Init_Table(isize);
    
22.         imap = new int*[isize];
    
23.         path = new int[isize];
    
24.         bselected = new bool[isize];
    
25.         for (int i=0;i<isize;i++)
    
26.         {
    
27.                 imap[i] = new int[isize];
    
28.                 bselected[i] = false;
    
29.                 for (int j=0;j<isize;j++)
    
30.                 {
    
31.                         if (i == j)
    
32.                         {
    
33.                                 imap[i][j] = 0;
    
34.                         }
    
35.                         else
    
36.                         {
    
37.                                 imap[i][j] = 1;
    
38.                         }
    
39.                 }
    
40.         }
    
41. }
    
42. void run_B(const int inow)
    
43. {
    
44.         for (int i=0;i<isize;i++)
    
45.         {
    
46.                 if (imap[inow][i] == 1 && bselected[i] == false)                //可行且未排过
    
47.                 {
    
48.                         path[iselected] = iTable[i];
    
49.                         bselected[inow] = true;
    
50.                         iselected++;
    
51.                         if (iTable[i] == iend)                //到达目标
    
52.                         {
    
53.                                 if (iselected + 1 == isize)                //是否差一个数字就全都排上
    
54.                                 {
    
55.                                         cout<<ibeg;
    
56.                                         for (int j=0;j<isize-1;j++)
    
57.                                         {
    
58.                                                 cout<<path[j];
    
59.                                         }
    
60.                                         cout<<"\t";
    
61.                                 }
    
62.                                 else
    
63.                                 {
    
64.                                         iselected--;
    
65.                                         bselected[inow] = false;
    
66.                                         continue;
    
67.                                 }
    
68.                         }
    
69.                         else
    
70.                         {
    
71.                                 run_B(i);
    
72.                         }
    
73.                         iselected--;
    
74.                         bselected[inow] = false;
    
75.                 }
    
76.         }
    
77. }
    
78. void B(int isize)
    
79. {
    
80.         Init_Map(isize);
    
81.         for (int i=0;i<isize;i++)
    
82.         {
    
83.                 for (int j=0;j<isize;j++)
    
84.                 {
    
85.                         if (iTable[i] != iTable[j])
    
86.                         {
    
87.                                 ibeg = iTable[i];
    
88.                                 iend = iTable[j];
    
89.                                 iselected = 0;
    
90.                                 run_B(i);
    
91.                         }
    
92.                 }
    
93.         }
    
94. }
    
95. void run_main()
    
96. {
    
97.         cout<<"Please let me know the N:";
    
98.         cin>>isize;
    
99. //        clock_t iTime = clock();
    
100.         B(isize);
     
101. //        cout<<"\n" <<clock() - iTime <<"\n";
     
102. }
     
103. int main()
     
104. {
     
105.         run_main();
     
106.         system("pause");
     
107. }
     

复制代码

fansfamily

可是，虽然结果也有一定的规律可寻，但我要的不止是这样。我又得想别的办法。想来想去，觉得失败的第一种也不是不可取……

1. 
   
2. #include <fstream>
   
3. #include <iostream>
   
4. #include <time.h>
   
5. using namespace std;
   
6. int *iTable;
   
7. int isize = 0;
   
8. 
   
9. struct doubleLink
   
10. {
    
11.         int iValue;
    
12.         doubleLink *pLast;
    
13.         doubleLink *pNext;
    
14. }dbLink;
    
15. doubleLink *istack;
    
16. void Init_doubleLink(int isize,doubleLink *dbLink)
    
17. {
    
18.         Init_Table(isize);
    
19.         if (!dbLink)
    
20.                 dbLink = new doubleLink;
    
21.         doubleLink *pNext = dbLink,*pLast;
    
22.         dbLink->pLast = NULL;
    
23.         for (int i=1;i<isize;i++)
    
24.         {
    
25.                 pNext->iValue = i;
    
26.                 pNext->pNext = new doubleLink;
    
27.                 pLast = pNext;
    
28.                 pNext = pNext->pNext;
    
29.                 pNext->pLast = pLast;
    
30.         }
    
31.         pNext->iValue = isize;
    
32.         pNext->pLast = pLast;
    
33.         pNext->pNext = NULL;
    
34. }
    
35. void stack_add(const int iValue)
    
36. {
    
37.         if (!istack)
    
38.         {
    
39.                 istack = new doubleLink;
    
40.                 istack->iValue = iValue;
    
41.                 istack->pLast = NULL;
    
42.                 istack->pNext = NULL;
    
43.                 return;
    
44.         }
    
45.         doubleLink *pNext = istack,*pLast = NULL;
    
46.         int isFind = false;
    
47.         while(pNext)
    
48.         {
    
49.                 if(pNext->iValue == iValue)
    
50.                 {
    
51.                         isFind = true;
    
52.                 }
    
53.                 pLast = pNext;
    
54.                 pNext = pNext->pNext;
    
55.         }
    
56.         if (!isFind)
    
57.         {
    
58.                 pNext = new doubleLink;
    
59.                 pNext->iValue = iValue;
    
60.                 pNext->pLast = pLast;
    
61.                 pNext->pNext = NULL;
    
62.                 if (pLast)
    
63.                         pLast->pNext = pNext;
    
64.         }
    
65. }
    
66. void stack_del(const int iValue)
    
67. {
    
68.         doubleLink *pNext = istack,*pLast = NULL;
    
69.         while(pNext)
    
70.         {
    
71.                 if(pNext->iValue == iValue)
    
72.                 {
    
73.                         if (!pNext->pNext)
    
74.                         {
    
75.                                 delete[] pNext;
    
76.                                 pNext = NULL;
    
77.                                 if (pLast)
    
78.                                 {
    
79.                                         pLast->pNext = NULL;
    
80.                                 }
    
81.                                 else
    
82.                                 {
    
83.                                         istack = NULL;
    
84.                                 }
    
85.                         }
    
86.                         else
    
87.                         {
    
88.                                 pLast->pNext = pNext->pNext;
    
89.                                 pNext->pNext->pLast = pLast;
    
90.                                 delete[] pNext;
    
91.                                 pNext = NULL;
    
92.                         }
    
93.                         break;
    
94.                 }
    
95.                 pLast = pNext;
    
96.                 pNext = pNext->pNext;
    
97.         }
    
98. }
    
99. bool stack_find(const int iValue)
    
100. {
     
101.         doubleLink *pNext = istack;
     
102.         while(pNext)
     
103.         {
     
104.                 if(pNext->iValue == iValue)
     
105.                 {
     
106.                         return true;
     
107.                 }
     
108.                 pNext = pNext->pNext;
     
109.         }
     
110.         return false;
     
111. }
     
112. int icount = 0;
     
113. doubleLink *pTemp;
     
114. void run_A(int inow = 0)
     
115. {
     
116.         for (int i=inow;i<isize;i++)
     
117.         {
     
118.                 if (!stack_find(iTable[i]))
     
119.                 {
     
120.                         if (icount == isize)
     
121.                         {
     
122.                                 icount = 0;
     
123.                                 pTemp = istack;
     
124.                                 while (pTemp)
     
125.                                 {
     
126.                                         icount++;
     
127.                                         cout<<pTemp->iValue;
     
128.                                         pTemp = pTemp->pNext;
     
129.                                 }
     
130.                         }
     
131.                         icount++;
     
132.                         cout<<iTable[i];
     
133.                         stack_add(iTable[i]);
     
134.                         run_A(inow);
     
135.                         stack_del(iTable[i]);
     
136.                 }
     
137.         }
     
138.         cout<<"\t";
     
139. }
     
140. void A(int isize)
     
141. {
     
142.         Init_doubleLink(isize,istack);
     
143.         run_A();
     
144. }
     
145. void run_main()
     
146. {
     
147.         cout<<"Please let me know the N:";
     
148.         cin>>isize;
     
149. //        clock_t iTime = clock();
     
150.         A(isize);
     
151. //        cout<<"\n" <<clock() - iTime <<"\n";
     
152. }
     
153. int main()
     
154. {
     
155.         run_main();
     
156.         system("pause");
     
157. }
     

复制代码

看出来了吗？已排过的数字入堆，剩下的就是排列未入堆的数字，排完就出来。至于为什么是双链表，而不是单链表或数组？那是因为我至今还没实现过双链表，想实现看看^_^。

呼！终于搞定！历时……一个下午！！！挺不容易的，如有不当之处，希望大家看在我这么辛苦，这么诚心的诚意上，就算啦~~~~原谅…原谅…