全排列算法的递归与非递归实现

全排列算法是常见的算法，用于求一个序列的全排列，本文使用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}。以此类推。这显然是一个递归的过程。

#include
     #include
     void 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
    
     for (j = 
     0; j
     
      printf(
      "%d ", result[i][j]);        }        
      printf(
      "\n");    }    system(
      "pause");}
     
    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63

非递归实现

非递归实现全排列的思想是：

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,从后向前查找,找到第一个si < sj,如果i=0时依然没有找到，说明该序列已经最大，返回。
2,从后向前查找，找到第一个比si大的元素sk，交换si和sk。为了保证得到的是次小的序列，将序列si+1到sn-1逆向。
3,重复1、2两步直到退出

#include
     #include
     void 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++);        //找到第一个比后一个元素小的元素numbers[i]        if (n < 2)//当序列只有一个元素时直接退出            return 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
    
     for (j = 
     0; j
     
      printf(
      "%d ", result[i][j]);        }        
      printf(
      "\n");    }    system(
      "pause");}

转载地址：http://jihbi.baihongyu.com/

你可能感兴趣的文章

[关注大学生]李开复给中国计算机系大学生的7点建议