全排列序集的定位算法。

serrinashan

以6元全排列为例说明我的算法。
假定1，2，3，4，5，6 的全排列集是按字典排序法作降序排列的，求第234个排列P(234).

首先，将234化作阶乘进位制，234=1*5!+4*4!+3*3!+0*2!+0*1=14300(!).
然后将降序全排列集分为6段：
00001(!)~10000(!): 6XXXXX,
10001(!)~20000(!): 5XXXXX,
20001(!)~30000(!): 4XXXXX,
30001(!)~40000(!): 3XXXXX,
40001(!)~50000(!): 2XXXXX,
50001(!)~100000(!): 1XXXXX。
由于10000(!)<14300(!)<20000(!), 故P(234)位于上述第2段，即5XXXXX段.
再将5XXXXX分作5段：
10001(!)~11000(!): 56XXXX,
11001(!)~12000(!): 54XXXX,
12001(!)~13000(!): 53XXXX,
13001(!)~14000(!): 52XXXX,
14001(!)~20000(!): 51XXXX。
由于14000<14300, 可知P(234)位于上述第5段，即51XXXX段。
再将51XXXX分作 4段：
14001(!)~14100(!): 516XXX,
14101(!)~14200(!): 514XXX,
14201(!)~14300(!): 513XXX,
14301(!)~20000(!): 512XXX。
由于234=14300(!)，可知P(234)正好位于第3段段末，即513246.
所以答案是P(234)=513246.

欢迎大家指正点评，qq号：1395551724

hujunhua

6!-234+1=720-234+1=487
假定1，2，3，4，5，6 的全排列集是按字典排序法作升序排列的，求第487个排列P(487).

首先，将487化作阶乘进位制，487=4*5!+0*4!+1*3!+0*2!+1*1=40101(!).
然后将升序全排列集分为6段：
00001(!)~10000(!): 1XXXXX,
10001(!)~20000(!): 2XXXXX,
20001(!)~30000(!): 3XXXXX,
30001(!)~40000(!): 4XXXXX,
40001(!)~50000(!): 5XXXXX,
50001(!)~100000(!): 6XXXXX。
由于40000(!)<40101(!)<50000(!), 故P(487)位于上述第5段，即5XXXXX段.
再将5XXXXX分作5段：
40001(!)~41000(!): 51XXXX,
41001(!)~42000(!): 52XXXX,
42001(!)~43000(!): 53XXXX,
43001(!)~44000(!): 54XXXX,
44001(!)~50000(!): 56XXXX。
由于40000(!)<40101(!)<41000(!), 故P(487)位于上述第1段，即51XXXX段。
再将51XXXX分作 4段：
40001(!)~40100(!): 512XXX,
40101(!)~40200(!): 513XXX,
40201(!)~40300(!): 514XXX,
40301(!)~41000(!): 516XXX。
由于487=40101(!)，可知P(487)正好位于第2段段首，即513246.
所以答案是P(487)=513246.

hujunhua

hujunhua

本来还想编一个Mathematica程序的，找了一下，没找到阶乘进位函数，又不想手工写一个，罢了。