求全排列问题

基本思路就是：
1、判断是否到达数组末尾，若是，输出数组，返回。
2、否则依次取出片段数组的每个元素，对剩下的元素组成的片段数组再进行排列。

注意，生成第二步的剩余片段数组的技巧是将每个元素与片段首个元素互换，这样首个元素之后到数组末尾的连续元素 就是 剩余片段数组——当然，互换完了还要互换回来，否则 第二步的剩余片段数组 的内容就会混乱。

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. void swapArrayElements(char a[], int lhs, int rhs)  
4. {  
5.      char temp;  
6.      temp = a[lhs];  
7.      a[lhs] = a[rhs];  
8.      a[rhs] = temp;  
9. }  
10. void perm(char a[], int start, int end)  
11. {  
12.      int i, j;  
13.      if (start == end){  
14.                //输出排列结果   
15.                for (j = 0; j <= end; j++)  
16.                    putchar(a[j]);  
17.                putchar('/n');  
18.                return;  
19.      } else{  
20.               
21.             for (i = start; i <= end; i++){  
22.                 //将数组片段的各元素与首元素交换   
23.                 swapArrayElements(a, start, i);  
24.                   
25.                 //对交换后的，去掉首元素的数组片段进行全排列   
26.                 perm(a, start+1, end);  
27.                   
28.                 //交换回来  
29.                 swapArrayElements(a, start, i);  
30.             }  
31.      }  
32. }  
33. main()  
34. {  
35.       char a[] = {'A', 'B', 'C', 'D'};  
36.       perm(a, 0, 3);  
37.       system("pause");  
38. }  

分享到：