我想计算一组的幂集。因为我一次不需要整个powerset,所以最好懒惰地生成它。
例如:
powerset (set ["a"; "b"; "c"]) =
seq {
set [];
set ["a"];
set ["b"];
set ["c"];
set ["a"; "b"];
set ["a"; "c"];
set ["b"; "c"];
set ["a";"b"; "c"];
}
由于结果是一个序列,我更喜欢上面的顺序。我怎样才能在 F# 中以惯用的方式做到这一点?
编辑:
这就是我将要使用的(基于 BLUEPIXY 的回答):
let powerset s =
let rec loop n l =
seq {
match n, l with
| 0, _ -> yield []
| _, [] -> ()
| n, x::xs -> yield! Seq.map (fun l -> x::l) (loop (n-1) xs)
yield! loop n xs
}
let xs = s |> Set.toList
seq {
for i = 0 to List.length xs do
for x in loop i xs -> set x
}
感谢大家的出色投入。
最佳答案
let rec comb n l =
match n, l with
| 0, _ -> [[]]
| _, [] -> []
| n, x::xs -> List.map (fun l -> x ::l) (comb (n - 1) xs) @ (comb n xs)
let powerset xs = seq {
for i = 0 to List.length xs do
for x in comb i xs -> set x
}
演示
> powerset ["a";"b";"c"] |> Seq.iter (printfn "%A");;
set []
set ["a"]
set ["b"]
set ["c"]
set ["a"; "b"]
set ["a"; "c"]
set ["b"; "c"]
set ["a"; "b"; "c"]
val it : unit = ()
关于f# - 懒惰地生成powerset,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8164364/