Permutations

算法输入：正整数n

算法输出：数1到n的所有可能全排列

算法思想：假定可以产生n-1个数的所有排列，那么可以用扩展的方法生成1到n的排列。方法如下：生成2到n的排列，并且每个排列前面加上数1，接下来生成数1，3， 4，…，n的所有排列。并且在每个排列的前面加上数2。重复这个过程知道最后生成1，2，…，n-1的所有排列，并在每个排列的前面加上数n。

注意事项：函数调用的写法。对于交换的算法，必须要传入你要交换的地址，否则的话，如果采用下面的写法，只是调换了子程序的，主函数的两个元素的顺序没有变：

void swap(int dataone, int datatwo)
{
    int tmp = dataone;
    dataone = datatwo;
    datatwo = tmp;
}

算法代码：

#include<stdio.h>
#include<malloc.h>

void permutations(int *a, int m, int n);
void exchange(int *a, int m, int n);
void swap(int *dataone, int *datatwo);

int main()
{
    int n = 4;
    int i, *p;
    p = (int*)malloc(n*(sizeof(int)));
    //将1到n的数字赋值到数组内
    for (i = 0; i < n; ++i)
    {
        p[i] = i + 1;
    }
    permutations(p, 0, n);
}

//生成m到n的数字的排列组合
void permutations(int *a, int m, int n)
{
    int i,j;
    if(m == n)
    {
        for(i = 0;i < n; i++)
            printf("%d", a[i]);
        printf("\n");
    }
    else
    {
        for(j = m;j < n; j++)
        {
            exchange(a, m ,j);
            permutations(a, m + 1, n);
            swap(&a[j], &a[m]);  //必须加上取地址符号
        }
    }
}

void exchange(int *a, int m, int n)
{
    int tmp = a[m];
    a[m] = a[n];
    a[n] = tmp;
}

void swap(int *dataone, int *datatwo)
{
    int tmp = *dataone;
    *dataone = *datatwo;
    *datatwo = tmp;
}