Генерация powerset лениво - PullRequest
Новая
       24

Генерация powerset лениво

4 голосов
/ 17 ноября 2011

Я хочу рассчитать 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 #?

EDIT:

Это то, что я собираюсь использовать (основываясь на ответе 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
    }

Спасибо всем за отличный вклад.

Ответы [ 3 ]

8 голосов
/ 17 ноября 2011 
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 = ()
4 голосов
/ 17 ноября 2011

С F # для ученых , слегка изменено, чтобы быть ленивым 

let rec powerset s = 
  seq {
    match s with
    | [] -> yield []
    | h::t -> for x in powerset t do yield! [x; h::x]
  }
0 голосов
/ 17 ноября 2011

Вот другой подход, использующий математику вместо рекурсии: 

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