生成懒惰的幂集

Question

我希望计算一个集合的幂集。因为我不需要一次性获取整个幂集，所以最好是惰性生成它。

例如：

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
    }

感谢大家提供的精彩意见。

- pad

Answer 1

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

- BLUEPIXY

---

请注意，你可以让 comb 函数返回一个序列，这在某些情况下可以减少计算量，特别是当不需要枚举整个幂集时。 - kvb

Answer 2

来自F# for Scientists，稍作修改使其更简洁易懂。

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

- Daniel

---

这很美好且高效。唯一的问题是顺序不正确 :) - pad

Answer 3

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

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

- Gus

---

请按照上述顺序翻译。 - BLUEPIXY

我明白，但它说“我更喜欢”。然而，我的意图主要是展示一种不同的方法，使用数学但仍然懒惰。 - Gus