全排序算法
1 /** 2 * 对arr数组中的begin~end进行全排列 3 * 4 * 比如： 5 * arr = {1,2,3} 6 * 第一步：执行 perm({1,2,3},0,2),begin=0,end=2; 7 * j=0,因此执行perm({1,2,3},1,2),begin=1,end=2; 8 * j=1,swap(arr,0,0)-->arr={1,2,3}, perm({1,2,3},2,2),begin=2,end=2; 9 * 因为begin==end，因此输出数组{1,2,3} 10 * swap(arr,1,1) --> arr={1,2,3}; 11 * j=2,swap(arr,1,2)-->arr={1,3,2}, perm({1,3,2},2,2),begin=2,end=2; 12 * 因为begin==end，因此输出数组{1,3,2} 13 * swap(arr,2,1) --> arr={1,2,3}; 14 * j=1,swap(arr,0,1) --> arr={2,1,3}, perm({2,1,3},1,2),begin=1,end=2; 15 * j=1,swap(arr,1,1)-->arr={2,1,3} perm({2,1,3},2,2),begin=2,end=2; 16 * 因为begin==end，因此输出数组{2,1,3} 17 * swap(arr,1,1)--> arr={2,1,3}; 18 * j=2,swap(arr,1,2)后 arr={2,3,1},并执行perm({2,3,1},2,2),begin=2,end=2; 19 * 因为begin==end，因此输出数组{2,3,1} 20 * swap(arr,2,1) --> arr={2,1,3}; 21 * swap(arr,1,0) --> arr={1,2,3} 22 * j=2,swap(arr,2,0) --> arr={3,2,1},执行perm({3,2,1},1,2),begin=1,end=2; 23 * j=1,swap(arr,1,1) --> arr={3,2,1} , perm({3,2,1},2,2),begin=2,end=2; 24 * 因为begin==end，因此输出数组{3,2,1} 25 * swap(arr,1,1) --> arr={3,2,1}; 26 * j=2,swap(arr,2,1) --> arr={3,1,2},并执行perm({2,3,1},2,2),begin=2,end=2; 27 * 因为begin==end，因此输出数组{3,1,2} 28 * swap(arr,2,1) --> arr={3,2,1}; 29 * swap(arr,0,2) --> arr={1,2,3} 30 * 31 * @param arr 32 * @param begin 33 * @param end 34 */
1 #include <stdio.h> 2 3 void swap(int *a, int *b) 4 { 5 int tmp; 6 tmp = *a; 7 *a = *b; 8 *b = tmp; 9 } 10 11 void perm(int arr[], int begin, int end) 12 { 13 int i, j; 14 if(begin == end) 15 { 16 for(i = 0; i < end; i++) 17 { 18 printf("%d ", arr[i]); 19 } 20 printf(" "); 21 } 22 else 23 { 24 for(j = begin; j < end; j++) 25 { 26 swap(arr+begin, arr+j); 27 perm(arr, begin+1, end); 28 swap(arr+begin, arr+j); 29 } 30 } 31 } 32 33 int main(void) 34 { 35 int a[] = {1, 2, 3, 4}; 36 37 perm(a, 0, sizeof(a)/sizeof(a[0])); 38 39 return 0; 40 }