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，并且还包含子集本身。