8 people like it.

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

More information

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