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 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 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
   (+0 other overloads)
Console.WriteLine(value: string) : unit
   (+0 other overloads)
Console.WriteLine(value: obj) : unit
   (+0 other overloads)
Console.WriteLine(value: uint64) : unit
   (+0 other overloads)
Console.WriteLine(value: int64) : unit
   (+0 other overloads)
Console.WriteLine(value: uint32) : unit
   (+0 other overloads)
Console.WriteLine(value: int) : unit
   (+0 other overloads)
Console.WriteLine(value: float32) : unit
   (+0 other overloads)
Console.WriteLine(value: float) : unit
   (+0 other overloads)
Console.WriteLine(value: decimal) : unit
   (+0 other overloads)
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
Console.ReadLine() : string
Raw view Test code New version

More information

Link:http://fssnip.net/6C
Posted:13 years ago
Author:zecl
Tags: computation builder , permutation , combination