F# 幂集函数

Question

returns 集合（列表）的幂集下方的函数。

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

我不明白为什么它会起作用。我理解递归。我也了解 List.collect 的工作原理。我知道递归会一直持续到 powerset returns [[]] 的一个实例。但是，我尝试跟踪该点之后的返回值，但我从未获得完整的幂集。

Answer 1

计算幂集的算法是这样的：

我们称原始集（又名 "input"）为 A。让我们从那个集合中挑出一个项目，称之为 x。现在，A 的幂集（称之为 P(A)）是 A 的所有子集的集合。我们可以认为 A 的所有子集都由两组组成：包含 x 的子集和不包含 x 的子集。很容易看出，不包含x的子集都是A - x的可能子集（A，排除x）：

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

我们如何获得包含 x 的 A 的所有子集？将所有不包含 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 }

这就是代码示例中最后一行的作用：它通过调用 powerset xs 计算 P(A-x)，然后为每个子集添加一个 x，并且还包括子集本身。

F# 幂集函数

F# Powerset Function

recursion

f#

powerset