2 people like it.

Generate Powerset using bit pattern

Generate the powerset of a set using a bit pattern.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

let powerset l =
    let s = ((l |> List.length) |> pown 2) - 1
    [0..s] |> 
    List.map (fun i -> l |> 
                       List.mapi (fun a b -> if (pown 2 a) &&& i <> 0 then Some(b) else None) |> 
                       List.choose id)


// powerset [1;2;3] = [[]; [1]; [2]; [1; 2]; [3]; [1; 3]; [2; 3]; [1; 2; 3]]
val powerset : l:'a list -> 'a list list

Full name: Script.powerset
val l : 'a list
val s : 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 pown : x:'T -> n:int -> 'T (requires member get_One and member ( * ) and member ( / ))

Full name: Microsoft.FSharp.Core.Operators.pown
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val i : int
val mapi : mapping:(int -> 'T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.mapi
val a : int
val b : 'a
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val choose : chooser:('T -> 'U option) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.choose
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
Raw view Test code New version

More information

Link:http://fssnip.net/gc
Posted:11 years ago
Author:Muigai
Tags: powerset bitwise and lists

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.