1

我想找到Powerset

幂集 [1;2;3] = = [[]; [3]；[2]；[2; 3]; [1]；[1; 3]; [1; 2]; [1; 2；3]]

let rec powerset = function
    | [] -> []
    | x::xs -> List.map (fun ys -> xs) xs::powerset (xs)

我的代码有问题，这就是我的输出现在的样子。

验证它：int list list list = [[[2; 3]; [2; 3]]; [[3]]；[]]

4

1 回答 1

3

其他人已经指出了一个使用序列表达式并懒惰地枚举集合的链接。这就是我解决问题的方法（请注意，使用for内部序列理解没有任何不纯或无功能的地方——它只是生成结果序列的一种方式）：

let rec powerset s = seq {
    match s with
    | [] -> yield []
    | h::t -> for x in powerset t do yield! [x; h::x] }

也就是说，这可以很容易地转换为返回列表并使用高阶函数的代码：

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

空集的幂集是具有单个元素的集合[]（请注意，这在您的代码段中是错误的）。为了生成 的幂集x::xs，我们首先生成 的幂xs集，然后为生成的幂集的每个单个元素返回两个集合——一个是子集，另一个是添加x元素的子集。（这是使用List.collectwhich 完成的，就像调用List.map后跟List.concat.）

于 2013-05-30T01:31:37.777 回答