4 people like it.
Like the snippet!

The Dominator of Array

The dominator of array A is the value that occurs in more than half of the elements of A. It is a zero-indexed based array consisting of N integers (A [] with N length). To find the index array of the dominator from a A [], we can use a helpful function from Seq module call 'Seq.groupBy' to mitigate the implementation of a solution.

 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:

module Dominator =
  
  /// A dominator occurs in more than half of an array's length
  let dominator (arr: int []) = 
    // Define an index seq
    let seqIndex  = Seq.init (arr.Length) id
    // Create groups based on key (i.e., the elements of the original arr)
    let seqGroups = Seq.groupBy(fun i -> arr.[i]) seqIndex
    seqGroups 
      // Find all the groups that the keys' occurrence is more than half of the original arr
      |> Seq.filter(fun x -> (snd x) |> Seq.length >= arr.Length/2) 
      // Convert the result as an index array of the dominator
      |> Seq.map snd |> Seq.concat |> Array.ofSeq

  // Testing cases
  let testArray1 = [|7;4;8;2;4;-1;4;4;4;4;6;4|]
  let testArray2 = [|0;2;2;4;0;2;0;0;2;2;2;8;2;2;2;0;0;0|]
  let testArray3 = [|1;2;3;4|]

  (*Although sometimes returning an Option type would be desirable*)
  // [|1; 4; 6; 7; 8; 9; 11|]
  dominator testArray1
  // [|1; 2; 5; 8; 9; 10; 12; 13; 14|]
  dominator testArray2
  // [||]
  dominator testArray3

val dominator : arr:int [] -> int []

Full name: Script.Dominator.dominator

A dominator occurs in more than half of an array's length

val arr : int []

Multiple items
val int : value:'T -> int (requires member op_Explicit)

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

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

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

val seqIndex : seq<int>

module Seq

from Microsoft.FSharp.Collections

val init : count:int -> initializer:(int -> 'T) -> seq<'T>

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

property System.Array.Length: int

val id : x:'T -> 'T

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

val seqGroups : seq<int * seq<int>>

val groupBy : projection:('T -> 'Key) -> source:seq<'T> -> seq<'Key * seq<'T>> (requires equality)

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

val i : int

val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

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

val x : int * seq<int>

val snd : tuple:('T1 * 'T2) -> 'T2

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

val length : source:seq<'T> -> int

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

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

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

val concat : sources:seq<#seq<'T>> -> seq<'T>

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

module Array

from Microsoft.FSharp.Collections

val ofSeq : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofSeq

val testArray1 : int []

Full name: Script.Dominator.testArray1

val testArray2 : int []

Full name: Script.Dominator.testArray2

val testArray3 : int []

Full name: Script.Dominator.testArray3

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/fj
Posted:	12 years ago
Author:	Joel Huang
Tags:	sequence , dominator , seq.groupby