recursion - F# Powerset 函数

Question

下面的函数返回一个集合(列表)的幂集。

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) )是 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到它上面，还包括子集本身。