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

回答

相關問題