給定一個數組，要求輸出其全排列。
比如對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 閱讀(313)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎