LINQ Recipe No. 2-5: Mathematics and Statistics - How to Find the Dominator in an Array?

Contents

1. Introduction
2. Key Words
3. Problem
4. Solution
5. Discussion
5.1 Dominator
5.2 ToLookup()
6. Practice: Find the Dominator
7. Conclusions
8. Literature & Links

1. Introduction

We have reached LINQ recipe no. 5. In this new opportunity, we will understand and learn how to find the dominator -an element which its repetition over other elements is more than 50%-. Again, we will drawn on the ToLookup() standard LINQ operator to perform this interesting task. The example in the practice section will present a given integer elements on an array, then by using LINQPad we will be to find the denominator from those values.

2. Key Words

• Array
• Dominator
• LINQ
• LINQPad

3. Problem

Given an array of integer values, find its dominator element.

For example, the array of integer 

{5, 2, 7, 7, 7, 11, 7, 7}

the dominator must be 7 because it appears more 5 times (5/8 * 100 ~= 63%).

4. Solution

LINQ offers to the programmer a powerful and expressive language to perform simple and complex operations on data. In this particular case, LINQ ToLookup() standard operator will be used to create a collection with grouped elements.

5. Discussion

5.1 Dominator

The prominent element on given array with more than 50% of recurrence is named denominator (Mukherjee, 2014).

Given the array of integer elements 

{5, 2, 7, 7, 7, 11, 7, 7}

7 is its dominator: it appears 5 times, which is equivalent to approximately 63% respect to the other elements recurrence.

5.2 ToLookup()

The ToLookup() ("Enumerable.ToLookup", 2016) method creates a Lookup generic collection. This collection has a set of keys, each of those mapped to one or more values.

[Nota: More about this method on recipe How to Calculate the Percentile for each Element in an Array of Numbers.]

6. Practice: Find the Dominator

We have the integer array with elements:

{5, 2, 7, 7, 7, 11, 7, 7}

Then we need to calculate its dominator element. So, the LINQ source code to find the dominator is:

int[] values = {5, 2, 7, 7, 7, 11, 7, 7};

values.ToLookup (value => value)

.First(value => value.Count() > values.Length/2)

.Key.Dump("Dominator");

First, the ToLookup() method groups each element in the array by repetition:

Illustration 1. Grouped elements.

Second, with the First ("Enumerable.First(TSource)", 2016) method the first element that satisfies a specified condition -value => value.Count() > values.Length/2- from the Lookup collection returned by ToLookup() will be selected: value with its recurrence greater than the fifty percent.

On LINQPad we get this result:

Illustration 2. 7 as dominator element.

As expected, 7 is the denominator for this array of integers.

7. Conclusions

Our understanding of the dominator of an array was reinforced by creating an example on LINQ. We have seen that the solution is simple: basically one line of code with the use of two LINQ methods -ToLookup() -collection with grouped elements- and First() -recovery of the first element which met certain condition-.

In the next recipe we will explore and learn how to find the the minimum number of currency bills required for a given amount on a ATM.

8. Literature & Literature

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Enumerable.ToLookup Method (System.Linq) (2016, April 6). Retrieved from: https://msdn.microsoft.com/en-us/library/system.linq.enumerable.tolookup(v=vs.100).aspx
How to Calculate the Percentile for each Element in an Array of Numbers (2016, April 6). Retrieved from: http://ortizol.blogspot.com/2016/04/linq-recipe-no-2-4-mathematics-and-statictis-how-to-calculate-the-percentile-for-each-element-in-an-array-of-numbers.html
Enumerable.First(TSource) Method (IEnumerable(TSource), Func(TSource, Boolean)) (System.Linq) (2016, April 6). Retrieved from: https://msdn.microsoft.com/en-us/library/bb535050(v=vs.110).aspx

V