8 people like it.
Like the snippet!

Very Fast Permutations

I spent a lot of time this week profiling different permutation functions from various places on the internet. The following was by far the fastest:

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11:

module List = 

    // From: http://stackoverflow.com/questions/286427/calculating-permutations-in-f
    // Much faster than anything else I've tested

    let rec permutations = function
        | []      -> seq [List.empty]
        | x :: xs -> Seq.collect (insertions x) (permutations xs)
    and insertions x = function
        | []             -> [[x]]
        | (y :: ys) as xs -> (x::xs)::(List.map (fun x -> y::x) (insertions x ys))

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  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 permutations : _arg1:'a list -> seq<'a list>

Full name: Script.List.permutations

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val empty<'T> : 'T list

Full name: Microsoft.FSharp.Collections.List.empty

val x : 'a

val xs : 'a list

module Seq

from Microsoft.FSharp.Collections

val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect

val insertions : x:'a -> _arg2:'a list -> 'a list list

Full name: Script.List.insertions

val y : 'a

val ys : 'a list

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

val x : 'a list

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/4u
Posted:	4 years ago
Author:	Rick Minerich
Tags:	list , seq , sequences , collections , permutations , combinatorial , f#