回溯法——求排列数 收藏

view plaincopy to clipboardprint?
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 4 3
1 2 5 3 4
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 4 2
1 3 5 2 4
1 4 3 2 5
1 4 3 5 2
1 4 2 3 5
1 4 2 5 3
1 4 5 2 3
1 4 5 3 2
1 5 3 4 2
1 5 3 2 4
1 5 4 3 2
1 5 4 2 3
1 5 2 4 3
1 5 2 3 4
2 1 3 4 5
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 1 5 4 3
2 1 5 3 4
2 3 1 4 5
2 3 1 5 4
2 3 4 1 5
2 3 4 5 1
2 3 5 4 1
2 3 5 1 4
2 4 3 1 5
2 4 3 5 1
2 4 1 3 5
2 4 1 5 3
2 4 5 1 3
2 4 5 3 1
2 5 3 4 1
2 5 3 1 4
2 5 4 3 1
2 5 4 1 3
2 5 1 4 3
2 5 1 3 4
3 2 1 4 5
3 2 1 5 4
3 2 4 1 5
3 2 4 5 1
3 2 5 4 1
3 2 5 1 4
3 1 2 4 5
3 1 2 5 4
3 1 4 2 5
3 1 4 5 2
3 1 5 4 2
3 1 5 2 4
3 4 1 2 5
3 4 1 5 2
3 4 2 1 5
3 4 2 5 1
3 4 5 2 1
3 4 5 1 2
3 5 1 4 2
3 5 1 2 4
3 5 4 1 2
3 5 4 2 1
3 5 2 4 1
3 5 2 1 4
4 2 3 1 5
4 2 3 5 1
4 2 1 3 5
4 2 1 5 3
4 2 5 1 3
4 2 5 3 1
4 3 2 1 5
4 3 2 5 1
4 3 1 2 5
4 3 1 5 2
4 3 5 1 2
4 3 5 2 1
4 1 3 2 5
4 1 3 5 2
4 1 2 3 5
4 1 2 5 3
4 1 5 2 3
4 1 5 3 2
4 5 3 1 2
4 5 3 2 1
4 5 1 3 2
4 5 1 2 3
4 5 2 1 3
4 5 2 3 1
5 2 3 4 1
5 2 3 1 4
5 2 4 3 1
5 2 4 1 3
5 2 1 4 3
5 2 1 3 4
5 3 2 4 1
5 3 2 1 4
5 3 4 2 1
5 3 4 1 2
5 3 1 4 2
5 3 1 2 4
5 4 3 2 1
5 4 3 1 2
5 4 2 3 1
5 4 2 1 3
5 4 1 2 3
5 4 1 3 2
5 1 3 4 2
5 1 3 2 4
5 1 4 3 2
5 1 4 2 3
5 1 2 4 3
5 1 2 3 4
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 4 3
1 2 5 3 4
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 4 2
1 3 5 2 4
1 4 3 2 5
1 4 3 5 2
1 4 2 3 5
1 4 2 5 3
1 4 5 2 3
1 4 5 3 2
1 5 3 4 2
1 5 3 2 4
1 5 4 3 2
1 5 4 2 3
1 5 2 4 3
1 5 2 3 4
2 1 3 4 5
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 1 5 4 3
2 1 5 3 4
2 3 1 4 5
2 3 1 5 4
2 3 4 1 5
2 3 4 5 1
2 3 5 4 1
2 3 5 1 4
2 4 3 1 5
2 4 3 5 1
2 4 1 3 5
2 4 1 5 3
2 4 5 1 3
2 4 5 3 1
2 5 3 4 1
2 5 3 1 4
2 5 4 3 1
2 5 4 1 3
2 5 1 4 3
2 5 1 3 4
3 2 1 4 5
3 2 1 5 4
3 2 4 1 5
3 2 4 5 1
3 2 5 4 1
3 2 5 1 4
3 1 2 4 5
3 1 2 5 4
3 1 4 2 5
3 1 4 5 2
3 1 5 4 2
3 1 5 2 4
3 4 1 2 5
3 4 1 5 2
3 4 2 1 5
3 4 2 5 1
3 4 5 2 1
3 4 5 1 2
3 5 1 4 2
3 5 1 2 4
3 5 4 1 2
3 5 4 2 1
3 5 2 4 1
3 5 2 1 4
4 2 3 1 5
4 2 3 5 1
4 2 1 3 5
4 2 1 5 3
4 2 5 1 3
4 2 5 3 1
4 3 2 1 5
4 3 2 5 1
4 3 1 2 5
4 3 1 5 2
4 3 5 1 2
4 3 5 2 1
4 1 3 2 5
4 1 3 5 2
4 1 2 3 5
4 1 2 5 3
4 1 5 2 3
4 1 5 3 2
4 5 3 1 2
4 5 3 2 1
4 5 1 3 2
4 5 1 2 3
4 5 2 1 3
4 5 2 3 1
5 2 3 4 1
5 2 3 1 4
5 2 4 3 1
5 2 4 1 3
5 2 1 4 3
5 2 1 3 4
5 3 2 4 1
5 3 2 1 4
5 3 4 2 1
5 3 4 1 2
5 3 1 4 2
5 3 1 2 4
5 4 3 2 1
5 4 3 1 2
5 4 2 3 1
5 4 2 1 3
5 4 1 2 3
5 4 1 3 2
5 1 3 4 2
5 1 3 2 4
5 1 4 3 2
5 1 4 2 3
5 1 2 4 3
5 1 2 3 4

上面时运行结果，这里给出结果是为了分析程序运行的过程。

从运行结果来看，第一个排列时1 2 3 4 5，这是第一个递归过程完成返回的结果。第二个是1 2 3 5 4，这里时交换了set[4]和set[3]，之后，第二个递归过程完成，返回结果。 这样的分析过程可参考排列树的回溯。对于n个节点的集合，其排列树的叶子节点有n!个，每一个从根到叶子节点的路径即是一个排列。

程序的执行过程是根节点从最左边开始向下搜索子树，到叶子节点后，往上层回溯。

1 #include <stdio.h>
2 #define N 5
3
4 int set[N]={1,2,3,4,5};
5 int com[N];
6 void swap(int &a,int &b)
7 {
8 int tmp =a;
9 a = b;
10 b = tmp;
11 }
12 void comination(int t)
13 {
14 int i ;
15 if(t>N-1)
16 {
17 for(i = 0;i<N;i++)
18 printf("%d ",com[i]);
19 printf("/n");
20 return;
21 }
22 for(i=t;i<N;i++)
23 {
24 swap(set[i],set[t]);//每次递归里的for循环第一次都是set[t]和自己交换，因为t==i此时。
25 //对排列树的第t层，可以搜索的子树是从t~N－1,对于每一种替换，都有一种选择。
26 com[t] = set[t];
27 comination(t+1);
28 swap(set[t],set[i]);
29 }
30 }
31 int main()
32 {
33 comination(0);
34 }
~

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/06/16/4274306.aspx