2 people like it.

Yet another (combinatorial) way to compute the factorial

Compute the factorial of a given number by building the list of permutations of the list of first n numbers [1..n] and taking its length

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
// generic 2-arg currying function
let curry f x y = f(x,y)

// insert given element x into the list at all possible positions
// returns list of lists
let rec ins x = function
   | [] -> [[x]]
   | h::t -> (x::h::t)::(List.map (curry List.Cons h) (ins x t))

// computes all permutations of a given list of elements
// return list of lists
let rec perm = function
  | [] -> [[]]
  | h::t -> List.collect (ins h) (perm t)

// compute the factorian of a given number
// by building the list of permutations of the list 
// of first n numbers [1..n] and taking its length
let fact n = List.length (perm [1..n])

// even better way to write the same thing
let fact' = (..) 1 >> List.ofSeq >> perm >> List.length
val curry : f:('a * 'b -> 'c) -> x:'a -> y:'b -> 'c

Full name: Script.curry
val f : ('a * 'b -> 'c)
val x : 'a
val y : 'b
val ins : x:'a -> _arg1:'a list -> 'a list list

Full name: Script.ins
val h : 'a
val t : '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 map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
static member List.Cons : head:'T * tail:'T list -> 'T list
val perm : _arg1:'a list -> 'a list list

Full name: Script.perm
val collect : mapping:('T -> 'U list) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.collect
val fact : n:int -> int

Full name: Script.fact
val n : int
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val fact' : (int -> int)

Full name: Script.fact'
val ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
Next Version Raw view Test code New version

More information

Link:http://fssnip.net/gG
Posted:11 years ago
Author:Dmitry Soshnikov
Tags: factorial , tutorial