数字全排列生成算法（一）

最近由于面试需要，开始逐渐研究起算法来，全排列生成算法我一直没弄明白，今天趁着有时间，看了一下，觉得算法不是很复杂。下面介绍的是字典序法的全排列生成算法。
算法思路就是：
1】从序列的末端开始，找到第一个数组合（可以不必相邻），其中第一个数小于第二个数，比如：1 2 3 4，第一个组合是34，记录3的位置为i；
2】从i位置之后的元素中，从末端开始找一个大于它的最小数，就是4，交换这两个数；
3】将i位置之后的数全部逆序，这样就生成了字典顺序的下一个序列；
4】执行步骤1；
算法实现如下：

#include <stdio.h>
#include <stdlib.h>

int array_size = 0;
int *dic;
void show()
{
    int i=0;
    for(i=0; i<array_size; i++)
    {
        printf("%d ", dic[i]);
    }
    printf("\n");
}
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int start, int end)
{
    while(start < end)
    {
        swap(&dic[start], &dic[end]);
        start++;
        end--;
    }
}

int main(int argc, char *argv[])
{
    int size = atoi(argv[1]);
    int i, n = size, j;
    array_size = size;
    dic = (int *)malloc(size * (sizeof(int)));
    for(i=0; i<size; i++)
    {
        dic[i] = i+1;
    }
    show();
    i = n-1;
    while(i >= 0)
    {
        int max = 1000, cur = -1;
        for(j=n-1; j > i; j--)
        {
            if(dic[j] > dic[i] && dic[j] < max)
            {    
                cur = j;

                max = dic[j];
            }
        }
        if(cur != -1)
        {
            swap(&dic[i], &dic[cur]);
            reverse(i+1, n-1);
            show();
            i = n-1;
        }
        else
            i--;
    }
    free(dic);
    return 0;
}



执行结果如下：
[root@localhost ~]# ./per 4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1