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

该算法是根据插入法而来。

设想有 n 个数字, 先取第一个数字. 再取第二个数字, 第二个数可以放在第一个数的左或右面, 就是有 0, 1 两个选择. 再取第三个数, 放到前面选好的两个数字中, 可以放在最左, 中间, 最右, 就是有 0, 1, 2 三个选择. 嗯, 很自然吗. 忽然你想到了二进位, 八进位那些数系转换关系。可以设计这样一个数, ...xyz, 其中个位数 z 是二进位的, 也就是放第二个数的两个位置; 十位数 y 是三进位的, 代表放第三个数字的三个位子, 然后百位数是四进位, 千位数是五进位的, 依以类推." 没错, 这样设计的话, 如果 0 表示放於最左面的话, 则 "2021" 这个数就代表了排列五个元素 (abcde), 取一个 a, 然后第二个 b 放在 a 的右面成 ab, 取 c 放到最右面成为 abc, 取 d 放到最左面成 dabc; 最后 e 放到中间去成为 daebc. 至於 "2021" 这个特别的设计的数可以用2*5+ 0*4 + 2*3 + 1*2 这样的计算来映对到自然数的数列上去。

如求 4 个数的 4! = 24 个排列, 第 18 个排列可以这样求得, 18 除 2, 余数是 0, 所以第二个数放在第一个数的左面; 然后商 9 再除 3, 余数 0, 所以第三个数於在头两个数的最左; 最后 3 除以 4, 余数是 3, 因此第四个数要放在前三个数的第 4 个空位, 也就是最右面。

再如，如果要求1 2 3的全排列：

xyz     对应十进制   排列

0 0        6       3 2 1

0 1        1       3 1 2

1 0        2       2 3 1

1 1        3       1 3 2

2 0        4       2 1 3

2 1        5       1 2 3

代码实现如下：

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

int *array;

void show()
{
    int start = array[0];
    for(;;)
    {
        if(start != 0)
        {    
            printf("%d ", start);
            start = array[start];
        }
        else
            break;
    }
    printf("\n");
}

void insert_array(int num, int index)
{
    int start = 0, count = 0;
    if(index == 0)
    {
        array[num] = array[0];
        array[0] = num;
        return;
    }
    while(count < index)
    {
        start = array[start];
        ++count;
    }
    array[num] = array[start];
    array[start] = num;
    return;
}

int total_mul(int n)
{
    int sum = 1;
    while(n>1)
    {
        sum *= n;
        --n;
    }
    return sum;
}

void gen_list(int *list, int n)
{
    int rst=1, quo=1;
    int index = 0;
    int step = 2;
    while(n != 0)
    {
        quo = n/step;
        rst = n%step;
        list[index] = rst;
        index++;
        step++;
        n = quo;
    }
}
void init_array(int size)
{
    int i=0;
    array[0] = 1;
    for(i=1; i<size; i++)
        array[i] = 0;
}
int main(int argc, char *argv[])
{
    int num = atoi(argv[1]);
    array = (int *)malloc(sizeof(int) * (num+1));
    int *list = (int *)malloc(sizeof(int) * (num-1));
    int sum = total_mul(num);
    int i=0, j=0, start = 2;
    for(i=0; i < sum; i++)
    {
        gen_list(list, i);
        init_array(num+1);
        for(j=0, start=2; j < num-1;start++, j++)
        {
            insert_array(start, list[j]);
        }
        show();
    }
    free(array);
    free(list);    
    return 0;
}


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