作者yauhh (哟)
看板Prob_Solve
标题Re: [问题] 环状排列演算法
时间Mon Jan 23 20:32:04 2012
※ 引述《EdisonX (闭上眼的鱼)》之铭言：
: 目的是要穷举所有可能之环状排列，
: 一般排列 P(n,m)，可用递回或旋转法完成，
: 但若只需环状排列时，个数是 P(n,m)/n，
: 目前小弟之作法为过程中先纪录结果至一集合
: 再针对产生之排列去检查集合是否重覆，
: 如此不但速度慢，又吃记忆体，
: 不知这问题目前是否已有演算法可产生所有环状排列之可能？
: 感谢各位！
1234这一列数字有六个间隔,如果视为环状则有五个间隔.
加入一个数字5,则在视为环状时, 51234 与 12345 是同一组环状排列.
所以,在1234加入5应该产生 15234, 12534, 12354, 12345.
1只有一种环状排列. 1,加入2,也只有一种环状排列,由只将2放到1後面产生.
12,加入3,则是 132, 123.
产生1234的环状排列,是在123环状排列{123,132}中加入4.
123加入4产生 1423, 1243, 1234; 132加入4产生 1432, 1342, 1324.
所以1234的环状排列是{1423,1243,1234,1432,1342,1324}.
这样应该可以处理掉这个问题吧.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.231.65.98
1F：推 suhorng:不如1摆第一个,剩下全排列,像上篇推文那样... 01/23 20:55
2F：→ yauhh:上面那推文我没看懂。至少自己知道怎麽做 01/23 21:23
※ 编辑: yauhh 来自: 61.231.65.98 (01/23 21:38)
3F：→ EdisonX:谢谢 y 大指导，此法可正常生成无误。 01/24 08:37