8 people like it.
Like the snippet!

Sequence of all Subsets of a set

A function that returns a sequence of subsets generated by the power set of a specified set. The function use bit patterns to generate sets. for example the power set generated by a set with 3 elements set [1;2;3;] has 2^3 sets. each set in the power set is represented by the set bits in each of the integer from 0 to (2^3) -1

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

//using bit pattern to generate subsets
let max_bits x = 
    let rec loop acc = if (1 <<< acc ) > x then acc else loop (acc + 1)
    loop 0
        
let bit_setAt i x = ((1 <<< i) &&& x) <> 0
let subsets s = 
        let a = Set.toArray s in
        let len = (Array.length a)
        let as_set x =  set [for i in 0 .. (max_bits x) do 
                                if (bit_setAt i x) && (i < len) then  yield a.[i]]
        
        seq{for i in 0 .. (1 <<< len)-1 -> as_set i}

// Seq.iter (printf "%O") (subsets (set [1 .. 5])) ;;

val max_bits : x:int -> int32

Full name: Script.max_bits

val x : int

val loop : (int32 -> int32)

val acc : int32

val bit_setAt : i:int32 -> x:int -> bool

Full name: Script.bit_setAt

val i : int32

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

Full name: Script.subsets

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

val a : 'a [] (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 toArray : set:Set<'T> -> 'T [] (requires comparison)

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

val len : int

module Array

from Microsoft.FSharp.Collections

val length : array:'T [] -> int

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

val as_set : (int -> Set<'a>) (requires comparison)

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

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

val i : int

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<_>

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/ff
Posted:	12 years ago
Author:	isaiah perumalla
Tags:	sets , power sets , sequences , bit patterns , algorithms