permutations.fs

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let rec permute = function
  | [] -> [[]]
  | e::xs -> List.collect (distribute e) (permute xs)

let generatePermutations r (vs : _ []) =
  let inline swap f t =
    let tmp = vs.[f]
    vs.[f]  <- vs.[t]
    vs.[t]  <- tmp
  let rec ff r (vs : _ []) l =
    if l > vs.Length then
      r vs
    else
      ff r vs (l + 1)
      for i = l - 1 downto 1 do
        swap i (i - 1)
        ff r vs (l + 1)
      // TODO: Can this restore be removed?
      for i = 1 to l - 1 do
        swap i (i - 1)
  let vs = Array.copy vs
  if vs.Length > 1 then
    ff r vs 2
  else
    r vs

let permutations (vs : _ []) : _ [] =
  let ra = ResizeArray 16
  generatePermutations (fun vs -> ra.Add (Array.copy vs)) vs
  ra.ToArray ()

open FsCheck

// now () returns current time in milliseconds since start
let now : unit -> int64 =
  let sw = System.Diagnostics.Stopwatch ()
  sw.Start ()
  fun () -> sw.ElapsedMilliseconds

// time estimates the time 'action' repeated a number of times
let time repeat init action () =
  let inline cc i       = System.GC.CollectionCount i

  let input             = init ()

  System.GC.Collect (2, System.GCCollectionMode.Forced, true)

  let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2
  let b                 = now ()

  for i in 1..repeat do
    action input |> ignore

  let e = now ()
  let ecc0, ecc1, ecc2  = cc 0, cc 1, cc 2

  e - b, ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2

[<EntryPoint>]
let main argv =
  for i = 0 to 10 do
    let a vs = generatePermutations (fun _ -> ()) vs
//    let a vs = permutations vs
//    let a vs = vs |> List.ofArray |> permute 
    printfn "Checking count = %i" i
    let ms, cc0, cc1, cc2 = time 1 (fun () -> Array.init i id) a ()
    printfn " it took %d ms and (%d, %d, %d) cc" ms cc0 cc1 cc2

//    let vs = Array.init i id
//    let e = vs |> List.ofArray |> permute  |> List.sort |> List.map Array.ofList |> Array.ofList
//    let a = vs |> permutations |> Array.sort
//    if e <> a then
//      printfn "Failed for count = %i" i
    ()
    
  0