16 people like it.

Permutation and Combination

Permutation and Combination using ListBuilder.

Permutation and Combination using ListBuilder

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: ``` ``````type ListBuilder() = let concatMap f m = List.concat( List.map (fun x -> f x) m ) member this.Bind (m, f) = concatMap (fun x -> f x) m member this.Return (x) = [x] member this.ReturnFrom (x) = x member this.Zero () = [] member this.Combine (a,b) = a@b member this.Delay f = f () let list = ListBuilder() let rec permutations n lst = let rec selections = function | [] -> [] | x::xs -> (x,xs) :: list { let! y,ys = selections xs return y,x::ys } (n, lst) |> function | 0, _ -> [[]] | _, [] -> [] | _, x::[] -> [[x]] | n, xs -> list { let! y,ys = selections xs let! zs = permutations (n-1) ys return y::zs } let rec combinations n lst = let rec findChoices = function | [] -> [] | x::xs -> (x,xs) :: list { let! y,ys = findChoices xs return y,ys } list { if n = 0 then return! [[]] else let! z,r = findChoices lst let! zs = combinations (n-1) r return z::zs } ``````

Example

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: ``` ``````let x4P0 = permutations 0 [1;2;3;4] printfn "4P0 = %d" x4P0.Length x4P0 |> Seq.iter (fun x -> printfn "%A" x) Console.WriteLine ("-----") |> ignore let x4P2 = permutations 2 [1;2;3;4] printfn "4P2 = %d" x4P2.Length x4P2 |> Seq.iter (fun x -> printfn "%A" x) Console.WriteLine ("-----") |> ignore let x4C0 = combinations 0 [1;2;3;4] printfn "4C0 = %d" x4C0.Length x4C0 |> Seq.iter (fun x -> printfn "%A" x) Console.WriteLine ("-----") |> ignore let x4C2 = combinations 2 [1;2;3;4] printfn "4C2 = %d" x4C2.Length x4C2 |> Seq.iter (fun x -> printfn "%A" x) Console.ReadLine () |> ignore ``````
Multiple items
type ListBuilder =
new : unit -> ListBuilder
member Bind : m:'f list * f:('f -> 'g list) -> 'g list
member Combine : a:'b list * b:'b list -> 'b list
member Delay : f:(unit -> 'a) -> 'a
member Return : x:'e -> 'e list
member ReturnFrom : x:'d -> 'd
member Zero : unit -> 'c list

Full name: Script.ListBuilder

--------------------
new : unit -> ListBuilder
val concatMap : (('a -> 'b list) -> 'a list -> 'b list)
val f : ('a -> 'b list)
val m : 'a list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'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 concat : lists:seq<'T list> -> 'T list

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

Full name: Microsoft.FSharp.Collections.List.map
val x : 'a
val this : ListBuilder
member ListBuilder.Bind : m:'f list * f:('f -> 'g list) -> 'g list

Full name: Script.ListBuilder.Bind
val m : 'f list
val f : ('f -> 'g list)
val x : 'f
member ListBuilder.Return : x:'e -> 'e list

Full name: Script.ListBuilder.Return
val x : 'e
member ListBuilder.ReturnFrom : x:'d -> 'd

Full name: Script.ListBuilder.ReturnFrom
val x : 'd
member ListBuilder.Zero : unit -> 'c list

Full name: Script.ListBuilder.Zero
member ListBuilder.Combine : a:'b list * b:'b list -> 'b list

Full name: Script.ListBuilder.Combine
val a : 'b list
val b : 'b list
member ListBuilder.Delay : f:(unit -> 'a) -> 'a

Full name: Script.ListBuilder.Delay
val f : (unit -> 'a)
Multiple items
val list : ListBuilder

Full name: Script.list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val permutations : n:int -> lst:'a list -> 'a list list

Full name: Script.permutations
val n : int
val lst : 'a list
val selections : ('b list -> ('b * 'b list) list)
val x : 'b
val xs : 'b list
val y : 'b
val ys : 'b list
val xs : 'a list
val y : 'a
val ys : 'a list
val zs : 'a list
val combinations : n:int -> lst:'a list -> 'a list list

Full name: Script.combinations
val findChoices : ('b list -> ('b * 'b list) list)
val z : 'a
val r : 'a list
val x4P0 : int list list

Full name: Script.x4P0
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
property List.Length: int
module Seq

from Microsoft.FSharp.Collections
val iter : action:('T -> unit) -> source:seq<'T> -> unit

Full name: Microsoft.FSharp.Collections.Seq.iter
val x : int list
type Console =
static member BackgroundColor : ConsoleColor with get, set
static member Beep : unit -> unit + 1 overload
static member BufferHeight : int with get, set
static member BufferWidth : int with get, set
static member CapsLock : bool
static member Clear : unit -> unit
static member CursorLeft : int with get, set
static member CursorSize : int with get, set
static member CursorTop : int with get, set
static member CursorVisible : bool with get, set
...

Full name: System.Console
Console.WriteLine() : unit
Console.WriteLine(value: string) : unit
Console.WriteLine(value: obj) : unit
Console.WriteLine(value: uint64) : unit
Console.WriteLine(value: int64) : unit
Console.WriteLine(value: uint32) : unit
Console.WriteLine(value: int) : unit
Console.WriteLine(value: float32) : unit
Console.WriteLine(value: float) : unit
Console.WriteLine(value: decimal) : unit
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val x4P2 : int list list

Full name: Script.x4P2
val x4C0 : int list list

Full name: Script.x4C0
val x4C2 : int list list

Full name: Script.x4C2