F# combinations generator. Based on the series "Producing combinations" by Eric Lippert

combinations.fsx

(*
* 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