F#Powerset功能

Question

以下函数返回集合(列表)的powerset.

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

我不明白为什么它确实有效.我理解递归.我也理解List.collect是如何工作的.我知道递归将继续,直到powerset的实例返回[[]].但是,我尝试在该点之后跟踪返回的值,并且我从未获得完整的功率集.

Answer 1

计算功率集的算法如下:

让我们调用原始集(又名"输入")A.让我们从那个集合中挑选一个项目,然后调用它x.现在,A(调用它P(A))的powerset 是一组所有子集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它,并且还包括子集本身.