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

  全排列算法是常见的算法，用于求一个序列的全排列，本文使用C语言分别用递归与非递归两种方法实现，可以接受元素各不相同的输入序列。

  题目来自：

  Given a of , all .

  For ,

  [1,2,3] have the :

  [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个元素交换java全排列算法 LeetCode：Permutations（全排列算法的递归与非递归实现），然后后面的n-1个元素再次进行全排列。也就是说Sn的全排列可以写为{s0,Sn-1},{s1,Sn-1},…{sn,Sn-1}。以此类推。这显然是一个递归的过程。

  <pre class="prettyprint">#include

include

void swap(int a, int b)
{

int temp;

<p>

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