字典排序和组合数学

By | 2008-04-30

曾经有一个关于字典排序的题目,它是这样的:
现在有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个数,得到相应的排列。
程序在这里

编译:
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,a对应3,b对应4,c对应5,按照c b a的顺序排列,是5 4 3,那么最后你要的12345的第五个排列是12543。

发表评论

电子邮件地址不会被公开。 必填项已用*标注