11 people like it.

All subsets of a set

A function implemented using sequence expressions that returns all subsets of a specified set. The function is not optimized, but it is very easy to understand.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
module Set = 
  /// Returns all subset of a specified set. For example, for input [1;2;3],
  /// the result will be a set containing sets [1;2;3], [1;2], [1;3], [2;3]
  /// [1], [2], [3] and [].
  let rec subsets s = 
    set [ // Add current set to the set of subsets
          yield s
          // Remove each element and generate subset of 
          // that smaller set
          for e in s do
            yield! subsets (Set.remove e s) ]

// Sample usage
Set.subsets (set [1 .. 3])
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 subsets : s:Set<'a> -> Set<Set<'a>> (requires comparison)

Full name: Script.Set.subsets


 Returns all subset of a specified set. For example, for input [1;2;3],
 the result will be a set containing sets [1;2;3], [1;2], [1;3], [2;3]
 [1], [2], [3] and [].
val s : Set<'a> (requires comparison)
val set : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.set
val e : 'a (requires comparison)
val remove : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.remove
Multiple items
module Set

from Script

--------------------
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>
Raw view Test code New version

More information

Link:http://fssnip.net/5S
Posted:12 years ago
Author:Tomas Petricek
Tags: set , sequences , sequence expressions , subset