F#找到Powerset

Question

我想找到Powerset

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 = [[2；3；2；3]；[3]；[]]

Answer 1

其他人已经指出了使用序列表达式并懒洋洋地枚举集合的链接。这就是我解决问题的方法(请注意，在序列理解中使用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的powerset，我们首先生成xs的powerset，然后为生成的powerset的每个元素返回两组--一个是子集，另一个是添加了x元素的子集。(这是使用List.collect完成的，这类似于调用List.map，然后是List.concat。)