2 people like it.

# Distance sort

Sort collection of items based on criteria of closest distance between consecutive items. The resulting collection first element is one of two farthest items, the end element is the second of the farthest pair. For the collection of `n` items the distance function is called n*(n-1) /2 times. The distance for pair of items is assumed to not depend on items order.

 ``` 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: 35: 36: 37: 38: 39: 40: 41: ``` ``````let distanceSort (d: 't -> 't -> 'd when 'd: comparison) (items: #seq<'t>) = let arr = Array.ofSeq items let distancesMap = Map.ofList [ for i in 0 .. Array.length arr - 2 do for j in i + 1 .. Array.length arr - 1 -> (i, j), d arr[i] arr[j] ] let distanceByIndexes i1 i2 = let i1, i2 = if i1 < i2 then i1, i2 else i2, i1 distancesMap[i1, i2] let farthestIndexes = distancesMap |> Map.toArray |> Array.maxBy (fun (_, dist) -> dist) |> fst let startIndex = farthestIndexes |> fst let rec loop (sorted: int ResizeArray) (index: int) (unsorted: int ResizeArray) = match unsorted.Count with | 1 -> sorted.Add unsorted[0] | _ -> sorted.Add index unsorted.Remove index |> ignore let index' = unsorted.ToArray() |> Array.minBy (distanceByIndexes index) loop sorted index' unsorted let mutable allIndexes = ResizeArray [| 0 .. Array.length arr - 1 |] let mutable sortedIndexes = ResizeArray() loop sortedIndexes startIndex allIndexes sortedIndexes.ToArray() |> Array.map (fun i -> arr[i]) ``````
val distanceSort : d:('t -> 't -> 'd) -> items:#seq<'t> -> 'b [] (requires comparison)
val d : ('t -> 't -> 'd) (requires comparison)
val items : #seq<'t>
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>
val arr : 't []
module Array

from Microsoft.FSharp.Collections
val ofSeq : source:seq<'T> -> 'T []
val distancesMap : Map<(int * int),'d> (requires comparison)
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
interface IEnumerable
interface IComparable
interface IEnumerable<KeyValuePair<'Key,'Value>>
interface ICollection<KeyValuePair<'Key,'Value>>
interface IDictionary<'Key,'Value>
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
member Add : key:'Key * value:'Value -> Map<'Key,'Value>
member ContainsKey : key:'Key -> bool
...

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val ofList : elements:('Key * 'T) list -> Map<'Key,'T> (requires comparison)
val i : int
val length : array:'T [] -> int
val j : int
val distanceByIndexes : ('c -> 'c -> 'e) (requires comparison)
val i1 : 'c (requires comparison)
val i2 : 'c (requires comparison)
val farthestIndexes : int * int
val toArray : table:Map<'Key,'T> -> ('Key * 'T) [] (requires comparison)
val maxBy : projection:('T -> 'U) -> array:'T [] -> 'T (requires comparison)
val dist : 'd (requires comparison)
val fst : tuple:('T1 * 'T2) -> 'T1
val startIndex : int
val loop : (ResizeArray<int> -> int -> ResizeArray<int> -> unit)
val sorted : ResizeArray<int>
Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
type ResizeArray<'T> = System.Collections.Generic.List<'T>
val index : int
val unsorted : ResizeArray<int>
property System.Collections.Generic.List.Count: int with get