F＃Powerset函數

Question

下面的函數返回set（list）的powerset。

let rec powerset = function 
    | [] -> [[]] 
    | x::xs -> List.collect (fun sub -> [sub; x::sub]) (powerset xs) 

我不明白爲什麼它的工作原理。我瞭解遞歸。我也理解List.collect是如何工作的。我知道遞歸將繼續，直到powerset的一個實例返回[[]]。但是，我試圖追蹤那個點之後的返回值，並且我從來沒有獲得完整的功率集。

Answer 1

的算法來計算髮電機組是這樣的：

讓我們把原來設置（又名「輸入」）A。我們從中選出一個項目，稱之爲x。現在，A的powerset（稱爲P(A)）是一組A的所有子集。我們可以將A的所有子集看作由兩個組組成：包含x的子集和不包含x的子集。很容易看出，不包括x子集（排除A與x）的A - x所有可能的子集：

all subsets of A that don't include x = P(A-x) 

我們如何獲得的所有子集A是做包括x？通過把所有那些不包括x和堅持x到每一個！

all subsets of A that include x = { for each S in P(A-x) : S+x } 

現在我們只需要將兩者結合起來，我們讓自己P(A)：

P(A) = P(A-x) + { for each S in P(A-x) : S+x } 

這是在你的代碼示例的最後一行所做的：它計算P(A-x)通過調用powerset xs，然後對於這些子集中的每一個，都會粘貼一個x，並且還包含子集本身。