Monthly Archives: 四月 2008

字典排序和组合数学

曾经有一个关于字典排序的题目,它是这样的:
现在有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。

Nokia手机主题制作

今天左右无事,学习了一下Nokia的主题制作,我的手机系统是S40的,本想去下载网上流传的Nokia Series 40 Theme Studio 2.2,但是去http://www.forum.nokia.com看了一下,发现并没有下载,这样子找了好半天,才发现有一个称作Carbide.ui 3.2 Theme Edition的东西,点这里可以下载,看了好久,才发现Nokia 好像没有再发布Series 40 Theme Studio,而是用这个Carbide.ui Theme Edition取代了它,而且它支持S40系统,所以我就下载了它。

下载很快,安装之后,打开发现和Eclipse惊人的像,这才明白这个玩意是怎么做出来的,不过做的也和Eclipse一样,很友好,又充满了可自己定制的挑战,所以花了一段时间研究了一下,制作主题很简单,看它自带的说明就可以完成,我给自己的手机做了个主题,下面的图就是:

nokia_1

我只是改了一些基本的参数,没有做一些深层次的改变,它还支持程序图标,动画切换等的修改,总之很好很强大,实际装上主题之后发现很不错,等之后有空,做一个很强大的主题。

另外,我还研究了一下Nokia的主题文件.nth,其实就是一个zip压缩文件,里面主要的就是一个theme.xml文件,其他的都是这个文件引用的资源,这个文件形如下面:

nokia_2

一开始用一个xml30.dtd定义了文档类型,而30估计就是S40第三代用户界面的意思,这个xml30.dtd应该在所有S40第三代用户界面的手机上都有,而下面的Untitiled-1.jpg是我添加的文件,qgn_bg_sk_left.png则应该也是所有S40系统上都有的文件了。那么可以根据这些信息写一个自己的主题制作软件,也并不是不行。

算是对Nokia的S40主题制作有了一些浅显的了解了,S60没用过,所以也不想去尝试,就像前面说的,之后有空,好好做一个完整的主题。