Powerset

Powerset function followed by with tiny sample.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16:

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
    }
for st in Set.ofList [ 1..9] |> powerset  do
    printfn "%A" st

val powerset : s:Set<'a> -> seq<Set<'a>> (requires comparison)

Full name: Script.powerset

val s : Set<'a> (requires comparison)

val loop : (int -> 'b list -> seq<'b list>)

val n : int

val l : 'b list

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val x : 'b

val xs : 'b list

module Seq

from Microsoft.FSharp.Collections

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val xs : 'a list (requires comparison)

Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool
  ...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>

val toList : set:Set<'T> -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.toList

val i : int

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length

val x : 'a list (requires comparison)

val set : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.set

val st : Set<int>

val ofList : elements:'T list -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofList

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

Raw view Test code New version

More information

Link:	http://fssnip.net/b7
Posted:	12 years ago
Author:	notostraca
Tags:	set , powerset