一个关于字典排序的问题

题目是这样的：
现在有1，2，3，4，5，6，7，8，9，九个数，任意组合排成一个数，这个数中任两位都不一样，这些组合按照字典顺序排列，举例来说，123456789是第一个，123456798是第二个，123456879是第三个，依次下去，现在要求编写一个程序，问第i个数字是什么？

这个问题用到组合数学中的基本知识，无奈这个是计算机系的课程，电子系完全就不沾边，所以我当时也不可能答出来，现在，通过向Tarazed咨询，我写出下面的解法，这个解法是Tarazed告诉我的，非常感谢他，他的Blog在这里。

9个数的排列太多，我们先考虑123三个数字的排列，它们可能的排列如下：
123
132
213
231
312
321
那么，我们考虑其中每个数的百位和十位它右边的数比它小的个数，对于123来说，百位1右边是2和3，比它小的数的个数是0个，十位2右边是3，比它小的数的个数是0个，我们把这两个0几下来，作为一个中介数：00，和123结合起来写作：
123 00
那么相应，我们把剩下的数的中间数也写出来：
132 01
213 10
231 11
312 20
321 21
好，中间数都写完了，那么我们观察这些中介数的排列，我们可以看出，这些数是2进制的（逢二进一）0，1，2，3，……但是又和二进制不同，最高位可以是2，那么这种数在组合数学中是有专门名称的，叫做递增进位制数，它的特点是，从右向左，编号依次为第一位，第二位，第三位，……，第n位，而第n位的进位制是n+1进制，对应上面两位的数，第一位进位制是2进制，所以它最大是1，第二位进位制是3，所以它最大是2，那么我们根据这样的进位制，可以看出，这种中介数转化成十进制之后，就是0，1，2，3，4，5，那么这不就是我们要的第几个数吗？在组合数学中，证明了每一个中介数和相应的排列是一一对应的，那么，我们就可以根据要求的第几位数，得到它的中介数，然后进一步找到其对应的组合，而从第几位数推到中介数是很简单的，现在的问题，就是如何能通过中介数，得到相应得排列。

我们这次用1，2，3，4，四个数字的排列作为例子，我们先按照上面的方法，写出其排列对应的中介数，如下：
1234 000
1243 001
1324 010
1342 011
1423 020
1432 021
……
我们就写这么多，然后我们将4，3，2，1写下来：
4 3 2 1
————————
比如说我们得到的是021这个中介数，那么我们从左往右数021这个数，第一个得到的是0，那么我们从右往左数4321，数0个数，得到的是1，将其标记为1，因为它是我们第一个得到的，如下：
4 3 2 1
————————
1
数021，第二个得到的是2，那么我们还剩下432，从右往左数2位，得到的是4，那么我们把第二个得到的4标记为2，如下：
4 3 2 1
————————
2 1
再数021，第三个得到的是1，那么我们还剩下32，从右往左数1位，得到3，标记为3，如下：
4 3 2 1
————————
2 3 1
最后剩下的2我们标记为4，如下：
4 3 2 1
————————
2 3 4 1
下面的一行，是得到的排列序号，我们按照下面一行的序号1234，写出对应的上面一行的数，1对应的1，2对应的4，3对应的3，4对应的2，写出来如下：
1432
这个数正好是中介数021对应的排列。

通过中介数的生成和反推排列，我们解决了这个问题，我用C写了个小程序，输入要求的第i个数，得到相应的排列。
程序如下：


/* This program is written by Ender.
* If you have any question,please send email to thelastender@gmail.com
* File name: da.c
* Compile and Link: gcc -c da.c -o da.o && gcc da.o -o da
* */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define LENGTH 12
#define MAX_NUM 4000000000U

void getSISN(int * S, unsigned long n); //get the steadily increase scale number（得到递增进位制数，我只知道这么翻译了）

char TABLE[2][LENGTH] = { {'a','b','c','d','e','f','g','h','i','g','k','l'},
{0,0,0,0,0,0,0,0,0,0,0} };

int main(int argc,char * argv[])
{
if(argc < 2)
{
goto error1;
}
int l = strlen(argv[1]);
if(l > 10)
{
goto error2;
}
int i ;
unsigned long n = 0;
for(i=0;i {
int c = argv[1][i];
if(isdigit(c))
{
n = n*10 + (c - 48);
if(l == 10 && i == 0)
{
if( (c-48) >= 4 )
{
goto error2;
}
}
}
else
{
goto error2;
}
}
fprintf(stderr,"You want to find the %luth arrange type.\n",n);

int S[LENGTH] ;
for(i=0;i {
S[i] = 0;
}

getSISN(S,n);

fprintf(stderr,"The intermediary number is:\t");
for(i=(LENGTH-1);i>=0;i--)
{
fprintf(stderr,"%d ",S[i]);
}
fprintf(stderr,"\n");

i = LENGTH - 1;
while(S[i] == 0)
{
i--;
}

//fprintf(stderr,"i is %d.\n",i);
char * a = calloc(i+2,sizeof(char));


int len = i;
int k = 0;
int x = 0;
int y = 0;
for(i=len;i>=0;i--)
{
x = 0;
y = 0;
k = 0;
while(x < (S[i]+1))
{
if(TABLE[1][k] == 0)
{
x++;
}
else
{
y++;
}
k++;
}
a[i+1] = TABLE[0][x+y-1];
TABLE[1][x+y-1] = 1;
}
i=0;
while(TABLE[1][i] != 0 && i < l+2)
{
i++;
}
a[0] = TABLE[0][i];
fprintf(stderr,"Length is:\t%d.\n",len+2);

fprintf(stderr,"Result is:\t");
for(i=(len+1);i>=0;i--)
{
fprintf(stderr,"%c ",a[i]);
}
fprintf(stderr,"\n");

free(a);
goto successed;

error1:
fprintf(stderr,"Usage: %s [number]\n",argv[0]);
return 1;

error2:
fprintf(stderr,"error:\tInput format error\n");
fprintf(stderr,"error:\tThe biggest number supported is %u.\n",MAX_NUM);
fprintf(stderr,"error:\tand no other character\n");
return 2;

successed:
return 0;
}


void getSISN(int * S, unsigned long n)
{
int l = 0;
int k = 2;
unsigned long m;
m = n;
do
{
S[l] = m % k;
m = m / k;
l++;
k++;
}while(m != 0);

return ;
}



编译：
gcc -c da.c -o da.o && gcc da.o -o da
运行：
da [你要的第i个排列数]
这个程序并没有要求输入的时候指定位数，但是限制了最大的输入数字为3999999999，得到的结果如果不满足位数，那么将你所要的排列的最高n位（这里n是程序结果的位数），按照程序结果排列，把其他的位数按照从小到大排列在这n位前面即可，例如，如果你要求12345，五位数字的第5个排列，那么你运行程序 da 5，得到的结果是：
You want to find the 5th arrange type.
The intermediary number is: 0 0 0 0 0 0 0 0 0 0 2 1
Length is: 3.
Result is: c b a
然后你选出12345的高3位是345，按照c b a的顺序排列，是5 4 3，那么最后你要的12345的第五个排列是12543。

这篇文章包括程序版权归Ender所有，禁止商业用途，有任何问题联系thelastender@gmail.com