Skip to content

Instantly share code, notes, and snippets.

@iskeld

iskeld/combinations.fsx

Last active Aug 29, 2015
Embed
What would you like to do?
F# combinations generator. Based on the series "Producing combinations" by Eric Lippert
(*
* F# Implementation of the combinations generator, based on the series "Producing combinations" by Eric Lippert
* - http://ericlippert.com/2014/10/13/producing-combinations-part-one/
* - ...
* - http://ericlippert.com/2014/10/27/producing-combinations-part-five/
*)
open System.Collections
open System.Collections.Generic
module List =
let choosei chooser list =
let rec chooseInner list index =
match list with
| [] -> []
| h::rest ->
match chooser index h with
| None -> chooseInner rest (index + 1)
| Some x -> x::chooseInner rest (index + 1)
chooseInner list 0
type TinySet =
struct
val private bits: int
private new (b:int) = { bits = b }
static member Empty = new TinySet(0)
static member private isOutOfRange item = item < 0 || item > 31
member this.Contains(item:int) =
if TinySet.isOutOfRange item then false
else (this.bits &&& (1 <<< item)) <> 0
member this.Add(item:int) =
if TinySet.isOutOfRange item then invalidArg "item" "Item must be between 0 and 31"
new TinySet(this.bits ||| (1 <<< item))
member this.Remove(item:int) =
if TinySet.isOutOfRange item then invalidArg "item" "Item must be between 0 and 31"
new TinySet(this.bits &&& ~~~(1 <<< item))
member this.toSeq() = seq { 0 .. 31 } |> Seq.filter this.Contains
interface IEnumerable<int> with
member this.GetEnumerator() = this.toSeq().GetEnumerator()
interface IEnumerable with
member this.GetEnumerator() = this.toSeq().GetEnumerator() :> IEnumerator
end
let combinations (elements: 'a list) k =
let cons x y = x::y
let rec booleans n k =
match (n, k) with
| (0, 0) -> [[]]
| (n, k) when n < k -> []
| (n, k) ->
if k >= 0 then (booleans (n-1) (k-1) |> List.map (cons true)) else []
@ (booleans (n-1) k |> List.map (cons false))
let selectByPosition = List.choosei (fun idx shouldPick -> if shouldPick = true then Some elements.[idx] else None)
(booleans elements.Length k) |> List.map selectByPosition
let combinationsWithSet (elements: 'a list) k =
let rec indexSets n k =
match (n, k) with
| (_, 0) -> [ TinySet.Empty ]
| (n, k) when n < k -> []
| (n, k) ->
(indexSets (n-1) k)
@
((indexSets (n-1) (k-1)) |> List.map (fun s -> s.Add(n-1)))
let selectByIndex (set:TinySet) = set.toSeq() |> Seq.map (fun idx -> elements.[idx]) |> Seq.toList
(indexSets elements.Length k) |> List.map selectByIndex
let byBools = combinations [ 50; 60; 70; 80; 90 ] 3
let byBitSets = combinationsWithSet [ 50; 60; 70; 80; 90 ] 3
printfn "Combinations with booleans"
byBools |> List.iter (printfn "%A")
printfn "Combinations with bit sets"
byBitSets |> List.iter (printfn "%A")
let setsEqual = (byBitSets |> List.sort, byBools |> List.sort) ||> Seq.forall2 (=)
printfn "Sets equal = %A" setsEqual
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.