懒洋洋地生成powerset
问题描述:
我想计算一个集合的powerset。因为我一次不需要整个权力机构,所以最好懒惰地生成它。懒洋洋地生成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
}
DEMO
> 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 =()
答
这里的另一种方法,利用数学,而不是递归:
let powerset st =
let lst = Set.toList st
seq [0..(lst.Length |> pown 2)-1]
|> Seq.map (fun i ->
set ([0..lst.Length-1] |> Seq.choose (fun x ->
if i &&& (pown 2 x) = 0 then None else Some lst.[x])))
答
从F# for Scientists,稍加修改偷懒
let rec powerset s =
seq {
match s with
| [] -> yield []
| h::t -> for x in powerset t do yield! [x; h::x]
}
+0
这是美丽而高效的。唯一的问题是不正确的顺序:) – pad
请注意,您可以使'comb'返回一个序列,如果整个powerset未枚举,在某些情况下这将需要更少的计算。 – kvb
你说得对。 – BLUEPIXY