: → tropical72:有,目前看过最高效 (唯一 codepad 没跑到当的) 的演算 11/22 01:31 : → tropical72:法在 TAOCP Vol4, 我也看不懂,只是照 pseudo code 编 11/22 01:31 : → tropical72:http://codepad.org/812zGijk ,看懂的人麻烦解释一下 11/22 01:32 : → tropical72:另不知道是什麽原因要穷举所有子集合?光64bits要穷举完 11/22 01:39 : → tropical72:就要费很多时间,建议先确认你的方向是不是正确。 11/22 01:40 大略说一下 这其实是一个递回演算法的改进版 这个递回演算法是这样的: Permutations(list) 1. 如果 list 只有一个元素 {x} 则回传序列 {(x)}。 否则的话： 2. 去掉 list 的最後一个元素後递回呼叫 Permutations 取得所有排列 3. 将这最後一个元素插入在每个得到的排列的每个空间(含头尾)即可 例如三个元素时 呼叫 Permutations({1,2}) 得到 {(1,2), (2,1)} 再把 3 插进上面的每个排列的每个空间即为 {(1,2,3),(1,3,2),(3,1,2),(3,2,1),(2,3,1),(2,1,3)} 而四个元素则再把 4 插进上面每个排列的每个空间 就得到上面连结执行结果的 24 种了 这支程式它实际上是去计算现在这个排列到下个排列要交换哪两个相邻元素 有注意看的话你会发现所产生出来的序列 最後一个元素是呈之字形的顺序 (例如上面执行结果里的 4 就是这样) 这使得所产生的每个序列和下个序列之间都只有两个相邻元素对调 由此再配合上 X 和 Y 阵列的辅助计算就能用回圈的方式一一把所有组合列出来了 我没有细追不太清楚 但 Y 看起来好像是 i 下次要往哪个方向移 X 则看起来像是 i 在 1~i 中的位置... -- 先说我没看 TAOCP 的那一章节 (实验室里只有供着 Vol.1 和 Vol.2 而已...) 这是从输出的型式推测应该是这个演算法的 -- いああオレたちには见えてるモノがあるbデ きっと谁にも夺われないモノがあるはずさ け 开口一番一虚一実跳梁跋扈形影相吊yュL羊头狗肉东奔西走国士无双南柯之梦 歪も ぶ 　意味がないと思えるコトがある ラPきっとでも意図はそこに必ずある んの く 依依恋恋空前絶後疾风怒涛有无相生 ラH急転直下物情骚然愚者一得相思相爱 だが ろ 无意味じゃない ラ6あの意図が 恋た で 有为転変死生有命苍天已死黄天当立 !!6五里雾中解散宣言千错万综则天去私 のり --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.83