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的powerset (称为P(A))是一组A的所有子集。我们可以将A的所有子集看作是由两个组组成的:包含x的子集和不包含x的子集。很容易看到不包括x的子集都是A - x的所有可能子集(不包括x的A)：

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