递归实现全排列问题

递归实现全排列问题

• 问题描述

  全排列，举个例子，比如123三个数字吧，全排列集为{123，132，213，231，312，321}，现在将三个数字变为n个数字，打印出所有的可能。
  

• 问题分析

  既然要用递归解决问题，首先应该将问题细化，从小来入手，比如一个数字A，那么，就是A
  两个数字AB，那么就有AB，BA；
  三个数字ABC，就有ABC,ACB,BAC,BCA,CAB,CBA.这6种排列方式。
  我们发现：得数 = 当前指定数字 + 剩余指定数字。
  当 n = 1时，就是当前数字。
  

• 代码实现

/* 2.递归和分治 排列问题 */
#include <stdio.h>
#include <string.h>
int swap(int * n, int * m)
{
    int temp;
    temp = *n;
    *n = *m;
    *m = temp;
    return 0;
}
int perm(int a[],int n,int m)   //n从0开始，是当前指定数字位置，m是数组长度 
{
    if(n == m)      //n == m , 即：排序完毕。实际上m-n==1也可以，因为最后一个元素可以留下来，不用排。 
    {
        for(int i = 0; i < m; i++)
            printf("%d", a[i]);
        printf("\n");
    }
    else
    {
        int i;
        for(i = n; i < m; i++)
        {
            swap(&a[i],&a[n]);  // 更改指定数字 
            perm(a,n+1,m);      //继续余下数字的操作 
            swap(&a[i],&a[n]);  //还原数组 
        }
    }
}
int main()
{
    int a[5]={1,2,3,4,5};
    perm(a,0,5);
    return 0;
}

其中，变量n一直在递归函数中充当一个改变指定数字的作用，我们通过一个循环，将数组中所有元素均遍历一遍，即每个数字都当过首位数字，同理，余下的数字处理方式相同，然后得出一组数据，进行下一轮。
改变数组就是将当前数字放到首位，然后递归对余下数字操作，还原数组是因为数组顺序被打乱，无法遍历数组，故需要还原，这个题目看起来简单，其实代码实现过程还是有点难度的（对于本人来说，大牛请略），还是值得仔细思考的。