[閒聊] 排列
※ 引述《plko (我餓了)》之銘言：
> ※ 引述《yoco (道德勇氣)》之銘言：
> > 喔... 「假設」我有一個函數，只是假設，
> > 他可以吃一個陣列，然後幫我把這個陣列所有的排序印出來，比方說：
> 感謝<(_ _)>
> 本來想不通的點，這樣就很清楚了...
上面的 Clojure 版是 "組合"，如果是要排列的，大致說明如下
1. 使用陣列 Index 來排，其次使用 map 去對應，實際的陣列的內容
如一個陣列有 3 個值好了：
user=> (lex-permutations (range 3))
([0 1 2] [0 2 1] [1 0 2] [1 2 0] [2 0 1] [2 1 0])
它排出來的結果，上面的 0 1 2 其實是陣列的索引值，
也就是接下來再用這個索引值去對應實際的陣列內容。
( 這 lex-permutations 是 lazy 陣列 )
2. 對應的方法如下：
(defn permutations
"All the permutations of items, lexicographic by index"
[items]
(let [v (vec items)]
(map #(map v %) (lex-permutations (range (count v))))))
^^^^^^^^^^^^^^^^ 產生索引值陣列
這邊有兩層的 map 讓它對應實際的排列值。同上 map 亦為 lazy。
3. 而 lex-permutations 的運作原理是，
每次根據 "目前的索引陣列值" 產生 "下一個索引陣列值"，
如果產生不出來表示是最後一個了....
其公式如下 : ( 程式就不貼了 )
如 [0 1 2] 的下一個是 [0 2 1]
y <- 從右往左找出第一個順向排列的 (這邊 1 < 2 順向)，
無 y 時為最後一個
z <- 從右往左找出第一個大於 (v y) 之值的
交換 (v y) 及 (v z) 產生 [0 2 1]
接下來是一個迴圈並令 y = y+1，且 z 從陣列最後開始，
loop 條件 y<z，每次，交換(v y) (v z)，然後 y=y+1, z=z-1
這邊一開始就 y 和 z 的值相同，所以不同交換了。
而 [0 2 1] 下一個是 [2 0 1] 亦同
y
z
交換產生 [1 2 0]
y
z
迴圈交換 [1 0 2]
z y ( 因為 y > z 跳出 loop )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.74.159
PLT 近期熱門文章
PTT數位生活區 即時熱門文章
