懒洋洋地生成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 
    }

谢谢大家对出色的输入。

来源

2011-11-17 pad

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 =()

来源

2011-11-17 09:26:18 BLUEPIXY

请注意，您可以使'comb'返回一个序列，如果整个powerset未枚举，在某些情况下这将需要更少的计算。 – kvb

你说得对。 – BLUEPIXY

这里的另一种方法，利用数学，而不是递归：

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])))

来源

2011-11-17 13:11:48 Gustavo

请参阅“我更喜欢按照上述顺序。” – BLUEPIXY

我明白了，但它说“我更喜欢”。然而我的目的主要是展示一种不同的方法，用数学，但仍然懒惰。 – Gustavo

从F# for Scientists，稍加修改偷懒

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

来源

2011-11-17 14:15:06 Daniel

这是美丽而高效的。唯一的问题是不正确的顺序:) – pad

懒洋洋地生成powerset

回答

相关问题