懒惰地生成powerset [英] Generate powerset lazily

问题描述

我想计算一个集合的幂集.因为我一次不需要整个功率集，所以最好懒惰地生成它.

I want to calculate powerset of a set. Because I don't need the whole powerset at a time, it's better to generate it lazily.

例如:

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#中以一种惯用的方式做到这一点?

Since the result is a sequence, I prefer it in the above order. How can I do it in an idomatic way in F#?

这是我要使用的(基于BLUEPIXY的回答):

This is what I'm going to use (based on BLUEPIXY's answer):

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

这篇关于懒惰地生成powerset的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！