给定一个数组，要求输出其全排列。
比如对1 2 3，其全排列数为3!。
那么我们如何做呢？其实手写全排列就能发现规律，我们会如下写:
1 2 3
1 3 2
2 1 3
2 3 2
3 2 1
3 1 2
这有什么规律呢？其实我们写下的全排列是：1(2 3)! 和2(1 3)!和3(2 1)!
所以就是一个典型的递归问题了：
1 inline void swap(int *a, int *b) {
2 int temp = *b;
3 *b = *a;
4 *a = temp;
5 }
6
7 void do_permutation(int *a, int k, int n) {
8 int i;
9 if (k >= n - 1) {
10 for (i = 0; i < n; ++i) {
11 printf("%d ", a[i]);
12 }
13 printf("\n");
14 return;
15 }
16 for (i = k; i < n; ++i) {
17 swap(a + k, a + i);
18 do_permutation(a, k + 1, n);
19 swap(a + k, a + i);
20 }
21 }
22
23 void permutation(int *a, int n) {
24 do_permutation(a, 0, n);
25 }
posted on 2012-09-06 22:16
myjfm 阅读(305)
评论(0) 编辑 收藏 引用 所属分类:
算法基础