給定一個(gè)數(shù)組，要求輸出其全排列。
比如對(duì)1 2 3，其全排列數(shù)為3!。
那么我們?nèi)绾巫瞿兀科鋵?shí)手寫(xiě)全排列就能發(fā)現(xiàn)規(guī)律，我們會(huì)如下寫(xiě):
1 2 3
1 3 2
2 1 3
2 3 2
3 2 1
3 1 2
這有什么規(guī)律呢？其實(shí)我們寫(xiě)下的全排列是：1(2 3)! 和2(1 3)!和3(2 1)!
所以就是一個(gè)典型的遞歸問(wèn)題了：
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 閱讀(316)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法基礎(chǔ)