全排列算法的递归与非递归实现
全排列算法是常见的算法，用于求一个序列的全排列，本文使用C语言分别用递归与非递归两种方法实现，可以接受元素各不相同的输入序列。
题目来自leetcode：
Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
递归实现
对于序列Sn={s0,s1,…,sn},其全排列可以看做s0与后面的n-1个元素交换，然后后面的n-1个元素再次进行全排列。也就是说Sn的全排列可以写为{s0,Sn-1},{s1,Sn-1},…{sn,Sn-1}。以此类推。这显然是一个递归的过程。
swap(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;}void permut(int **result, int numbers[], int n, int *rows, int m){//完成下标为m到n的全排列int i;if (m == n){//已经处理到最后一个元素，递归返回(*rows)–;for (i = 0; i < n; i++)result[(*rows)][i] = numbers[i];}else{for (i = m; i < n; i++){swap(&numbers[m], &numbers[i]);//交换permut(result, numbers, n, rows, m + 1);//向后处理swap(&numbers[m], &numbers[i]);//再次交换}}}int **permute(int numbers[], int n, int *numRows){int **result, i;*numRows = 1;//计算全排列数for (i = n; i>1; i–)(*numRows) *= i;//分配结果数组result = (int **)malloc((*numRows)*sizeof(int *));for (i = 0; i<(*numRows); i++)*(result + i) = (int *)malloc(n*sizeof(int));int rows = *numRows;//从第一个元素开始排列permut(result, numbers, n, &rows, 0);return result;}int main(){int i, j;int numbers[3] = {1,2,2};int numRows = 0, n = 3;int **result = permute(numbers, n, &numRows);for (i = 0; i<numRows; i++){for (j = 0; j<n; j++){printf(“%d “, result[i][j]);}printf(“\n”);}system(“pause”);}非递归实现
非递归实现全排列的思想是：
1,将序列排序，生成最小序列Smin 2,然后找到比Smin大但比其他序列都小的序列Smin+1 3,反复执行2,直到序列最大
比如序列{2,1,3}，首先排序得到最小序列{1,2,3}，然后找到次小的序列{1,3,2}，，然后是{2,1,3}……以此类推直到序列{3,2,1}结束。
其算法是在序列{s0,s1,…si,sj,…sk,…,sn-1}中 1,从后向前查找,找到第一个sisj,如果i=0时依然没有找到，说明该序列已经最大，返回。 2,从后向前查找，找到第一个比si大的元素sk，交换si和sk。为了保证得到的是次小的序列，将序列si+1到sn-1逆向。 3,重复1、2两步直到退出
swap(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;}void sort(int numbers[], int n){//冒泡排序int i, j, k;for (i = 0; i < n; i++){for (j = i + 1; j < n; j++){if (numbers[i]>numbers[j])swap(&numbers[i], &numbers[j]);}}}void reverse(int numbers[], int i, int j){//逆置int p, q;for (p = i, q = j; p < q; p++, q–)swap(&numbers[p], &numbers[q]);}void store(int **result, int numbers[], int n, int row){//将序列存入结果数组中int i;for (i = 0; i < n; i++)result[row][i] = numbers[i];}int **permute(int numbers[], int n, int *numRows){int **result, i,j,row;*numRows = 1;for (i = n; i>1; i–)(*numRows) *= i;result = (int **)malloc((*numRows)*sizeof(int *));for (i = 0; i<(*numRows); i++)*(result + i) = (int *)malloc(n*sizeof(int));//首先对序列进行排序，找到最小序列sort(numbers,n);row = 0;while (true){store(result, numbers, n, row++);result;for (i = n – 2; i >= 0; i–){if (numbers[i] < numbers[i + 1])break;else if (i == 0)return result;}//找到从后面开始比numbers[i]大的第一个元素for (j = n – 1; j > i; j–){if (numbers[j] > numbers[i])break;}swap(&numbers[i], &numbers[j]);reverse(numbers, i + 1, n-1);}}int main(){int i, j;int numbers[3] = {1,2,3};int numRows = 0, n = 3;int **result = permute(numbers, n, &numRows);for (i = 0; i<numRows; i++){for (j = 0; j<n; j++){printf(“%d “, result[i][j]);}printf(“\n”);}system(“pause”);}
在你成功地把自己推销给别人之前，你必须百
