Re: [問題] n個元素的集合

[LPH66 (-858993460)]

: → 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
推 tropical72:謝謝 LPH 大的解說,補註一下,TAOCP vol4 有合法官網
→ tropical72:http://www.cs.utsa.edu/~wagner/knuth/ 有興趣可連.
→ tropical72:( 後來才注意到原來這是 perm. 不是 power set  XD)
→ bleed1979:旋轉法？C名題精選百則問題3-4
推 stimim:變數重新命名、迴圈分離、改變迴圈的方向之後變這樣:
→ stimim:http://codepad.org/gYupqgwd
→ stimim:希望有比較容易明白
推 tropical72:感謝 b 大. s大. 只是 Rotation Method 我從沒印像有
→ tropical72:計算層乘說,所以一開始完全連結不起來 XD
推 VictorTom:推~~