递归的应用——全排列算法

分治策略

设一组数R={r1,r2,r3....rn}为要进行全排列的n个元素，Ri=R-{ri}。将集合X中元素的全排列记为perm(X)。(ri)prem(X)表示在全排列perm(X)的每一个排列前面前面加上前缀ri得到的排列R的全排列可以归纳为：

    当n=1时，perm（R）=（r），其中r是集合R中唯一元素。

    当n>1时，perm（R）由（r1）perm（R1），（r2）perm（R2），....，（rn）perm（Rn）

   构成。

由归纳可已看出本题可以用递归分治的算法将问题分成一个一个得小模块进行求解。

EG：

   R={1,2,3,4}

ps：这里圆括号里面的顺序是不能变动的。有上数据可知符合分治递归的条件。

在上面的{1，2，3，4}中可以看出分治的到了内层{}中元素为一停止。

故当分治次数k和R中元素的数目m相等时为跳出条件。

并且每一层的分类次数为m-k+1.

实现代码如下

#include <stdio.h>
static int n = 0;
void swap(int *x,int *y)
{
    /* *x ^= *y;
    *y ^= *x;
    *x ^= *y;
    */

    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}
int allsort(int *array,int *start,int *end)
{
    int *p;
    if(start < end)
    {
        for(p = start ; p < end; ++p)
        {
            swap(start,p);
            allsort(array,start+1,end);
            swap(start,p);
        }
    }else{//start > end
        for(p = array;p < end ; ++p)
            printf("%d\t",*p);
        ++n;
        printf("\n");
    }
}
int main(int argc,char *argv[])
{
    int list[]={1,2,3,4,5};

    allsort(list,list,list+sizeof(list)/sizeof(int));
    printf("Total %d \n",n);
    return 0;
}