数学研发论坛

 找回密码
 欢迎注册
查看: 147|回复: 3

[原创] 全排列序集的定位算法。

[复制链接]
发表于 2018-1-2 14:20:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
以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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-1-4 08:54:18 | 显示全部楼层

验算:按升序重新计算

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.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-1-4 19:52:47 | 显示全部楼层

计算流程图

全排列定位计算程序图.PNG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-1-4 20:09:41 | 显示全部楼层
本来还想编一个Mathematica程序的,找了一下,没找到阶乘进位函数,又不想手工写一个,罢了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-1-18 09:55 , Processed in 0.074509 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表