LINQ Recipe No. 2-17: Collections - How to Find the Larger or Smaller Value of Sequences at Each Element Index

Contents

1. Introduction
2. Keywords
3. Problema
4. Solution
5. Discussion
5.1 Zip() standard query operator
6. Pratice: Denoting Bidding Values
7. Conclusions
8. Literature & Links

1. Introduction

With this new LINQ recipe the programmer will learn how to find the larger or smaller value from several given sequences. These sequences have the same length and are composed of numeral values. Particularly, the programmer is going to use, once again, the Zip() standard query operator from LINQ to accomplish this computation. In the practice section, the reader will know how to find the maximum and minimum bid values from the given sequences. LINQ is amazing!

2. Keywords

• Collection
• LINQ
• Sequence
• Standard query operator
• Zip()

3. Problem

Find the minimum or maximum value of several sequences at each element index.

4. Solution

In LINQ we find the Zip() standard query operator to apply some specified function to a sequence of elements; the function uses each index as input values.

5. Discussion

5.1 Zip() standard query operator

Zip() is a standard query operator; it's useful to apply some specified function to each element index of a sequence. Visually, it can viewed as 

Illustration 1. Zip() visual operation schema.

Notice that each index from seq1 has its corresponding index on seq2: the function operates over each index.

To exemplify it, this code concatenates the symbol and literal representations for numbers: 

int[] numbers = { 1, 2, 3 };

string[] words = { "One", "Two", "Three"};

var numbersAndWords = numbers.Zip(words, (n, w) =>

String.Format("{0} - {1}", n, w));

numbersAndWords.Dump("Numbers and Words");

Once executed in LINQPad, this is the result: 

Illustration 2. Zip() example.

6. Practice: Denoting Bidding Values

Suppose we have two collections to represent the bidding values for different items.

The purpose with this recipe is to learn how, by means of LINQ, to find the smaller and larger of bidding values.

LINQ file MinMaxBids.cs [Mirror 1][Mirror 2]: 

Lines 2 and 3 define two list of bid values as integer elements. Next, lines 6-8, we call Zip() function to find the maximum bids from sequence's indexes. Observe how the Math.Max() function is used to find the maximum between the two parameters bid1 and bid2.

Analogally, lines 11-13, compute the Math.Min() function to find the minimum of the two parameters -bid1 and bid2.

The output in LINQPad: 

Illustration 1. Minimum and maximum bids.

An extended version of this solution consists on multiple bid sequences (it's a generalized approach): 

LINQ file MinMaxBidsGeneralApproach.cs [Mirror 1][Mirror 2]: 

Four sequences are defined to contain bid values (lines 2-5). All these sequences are added to a list of lists (lines 8-12). Its purpose is to find the smaller and larger bid values using the Aggregate ("Enumerable.Aggregate(TSource) Method", 2016); basically, what this method does is apply an accumulator over a sequence.

Once executed, this is the resultant output in LINQPad: 

Illustration 3. Minimum and maximum bids (general approach).

Video tutorial: 

7. Conclusions

We have used the Zip() as programmatic mechanism to find the smaller or larger values from two sequences. This knowledge is useful for many applications which require this kind of computation for some type of values.

Next LINQ recipe is going to explain how to generate Armstrong Numbers and similar number sequences.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Enumerable.Zip(TFirst, TSecond, TResult) Method (System.Linq) (2016, julio 13). Retrieved from: https://msdn.microsoft.com/en-us/library/dd267698%28v=vs.100%29.aspx?f=255&MSPPError=-2147217396
Enumerable.Aggregate(TSource) Method (IEnumerable(TSource), Func(TSource, TSource, TSource)) (System.Linq) (2016, julio 13). Retrieved from: https://msdn.microsoft.com/en-us/library/bb548651(v=vs.110).aspx

O

LINQ Recipe No. 2-16: How to Pick Every nth Element from a Collection

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 Range(int, int) method
5.2 Skip() method
6. Practice: Picking Every nth Element from a Collection
7. Conclusions
8. Literature & Links

1. Introduction

A task like element selection, or more particularly pick every nth element, from a collection is a common problem that frequently appears in other problems such as randomizing, listing, or load distribution. In this LINQ recipe will demonstrate to the programmer how to write an idiomatic LINQ program to query a collection for finding every nth element.

2. Keywords

• Collection
• LINQ
• List
• Load distribution
• Query

3. Problem

Pick every nth element from a given sequence (without dividing the index to determine whether to include an element from the collection).

4. Solution

First, it's possible to divide the sequence's count property by the nth element, and then use Skip() method to bypass a specified number of elements in the sequence.

5. Discussion

5.1 Range(int, int) method

Range() method generates a sequence of number for a range. ("Enumerable.Range Method", 2016). For example: 

IEnumerable<int> cubes = Enumerable.Range(1, 10).Select( x => x * x * x);

Here, Range generates the range of numbers from 1 to 10 as counting, i.e., 10 numbers. Then Select() produces the 3rd power for each number from 1 to 10.

5.2 Skip() method

This method is used to bypass a given number of elements, and it returns the remaining elements of the sequence ("Enumerable.Skip(TSource)", 2016).

int[] grades = {53, 61, 97, 91, 89, 71};

IEnumerable lowerGrades = grades.OrderByDescending(g => g)
.Skip(3);

What we get with this expression is lower grades: in the first place, the sequence is sorted in descending order, then with Skip(3) the higher grades -97, 91, and 89- are skipped.

6. Practice: Picking Every nth Element from a Collection

Now it's time to write an idiomatic LINQ query in LINQPad to pick every nth element in a sequence.

LINQ file PickNthElement.linq [Alternative link][Alternative link]: 

With int n = 10; (line 2) we specify the nth element: in this case we will pick every 10th element. In line 5 we request a list of 100 numbers -range 1 to 100.

It's required a data structure, in this case a list, to store the nth elements; that is define in line 8: List<int> nthElements = new List<int>();.

With this in mind, we got lines 11-13: here the expression Enumerable.Range(0, numbers.Count()/n) produces a range from 0 to 9; its purpose is allow the iteration of each nth element in the numbers list.

Now the code numbers.Skip(k*n).First() skips the k*n elements in numbers, and chooses the first element of the remaining elements generated by Skip(k*n).

Let's play an execution for this amazing LINQ code: 

7. Conclusions

An operation like pick an element from a collection is a common task; this recipe has showed us how to pick every nth element from a sequence by using the Skip() and First() methods.

The next recipe, the LINQ programmer will learn how to find the larger or smaller of several sequences at each index.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Enumerable.Range Method (Int32, Int32) (System.Linq) (2016, July 7). Retrieved from: https://msdn.microsoft.com/en-us/library/system.linq.enumerable.range(v=vs.110).aspx
Enumerable.Skip(TSource) Method (IEnumerable(TSource), Int32) (System.Linq) (2016, July 7). Retrieved from: https://msdn.microsoft.com/en-us/library/bb358985%28v=vs.110%29.aspx?f=255&MSPPError=-2147217396

V

LINQ Recipe No. 2-15: Recursive Series and Patterns - How to Generate the Power Set of a Set

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 Power set
6. Practice: Generating a Power Set of a Given Set
7. Conclusions
8. Literature & Links

1. Introduction

We continue to discover the pretty amazing capabilities of LINQ as functional programming language. In this opportunity we are going to learn how to generate the power set of a given set. To learn this, we need to go back, i.e. to the previous recipe, and review how to generate partial permutations for a given set of elements. As we will verify soon, this practical knowledge is useful in discrete mathematics and consequently in computer science.

2. Keywords

• Discrete mathematics
• Functional programming
• Partial permutation
• Power set
• Set

3. Problem

Generate the power set of a given set.

4. Solution

Partial permutations are useful to generate the power set of a given set.

5. Discussion

5.1 Power set

In simple terms, a power set is a set of all subsets of a given set, including the empty set. By the same token, a power set is formally defined as 

For example, if we have the set S with elements {x, y, z} its power set is equal to 

{{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}

We can also compute the number of subsets of S with 

where n is the number of elements in S. Hence, S has 8 subsets.

6. Practice: Generating a Power Set of a Given Set

It's time for LINQ and LINQPad! We are going to create a LINQ code implementation to compute the subsets of set -i.e., its power set-.

For the purpose of demonstrating this recipe, it's important to mention that the GeneratePartialPermutation(string) method from LINQ Recipe No. 2-14: How to Generate Permutations will be used to generate the partial permutations for the given set.

Then, these partial permutations will produce the element pairs to generate all the elements -sets- of the power set.

LINQ file PowerSet.linq [Alternative link][Alternative link]: 

The GeneratePartialPermutation(string) method is declared in lines 2-6. It produces partial permutations for a given string of characters; for example, the "abc" has three partial permutations: "abc", "bac", and "cab".

Equally important, in lines 9-40, the Main method performs all these operations: 

• Line 12: Set of characters to generate its power set.
• Line 15: Generates partial permutations for "abc".
• Lines 20-31: It creates the element pairs for each partial permutation.
• Lines 34-49:
• Line 35: Sorts each subset in ascending order.
• Line 37: Deduplicates subsets.
• Line 38: Sorts each subset by length in ascending order.
• Line 39: Outputs the resultant power set on LINQPad output window.

As an alternative code explanation, we have this short video tutorial with a execution demo: 

7. Conclusions

This recipe has taught us how to generate the power set of a given set using a functional programming approach. At first it can appears messy, but once we understand the LINQ standard operators, the task is easy to accomplish.

Next recipe will teach us how to pick every element in an collection. That's will be pretty amazing!

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Power set (2016, July 7). Retrieved from: https://en.wikipedia.org/wiki/Power_set
Power Set (2016, July 7). Retrieved from: https://www.mathsisfun.com/sets/power-set.html
Power Set (2016, July 7). Retrieved from: http://mathworld.wolfram.com/PowerSet.html
LINQ Recipe No. 2-14: How to Generate Permutations (2016, July 7). Retrieved from: https://ortizol.blogspot.com.co/2016/07/linq-recipe-no-2-14-how-to-generate-permutations.html

V

LINQ Recipe No. 2-14: How to Generate Permutations

Contents

1. Introduction
2. Keywords
3. Problema
4. Solution
5. Discussion
5.1 Permutations
6. Practice: Generating Permutations
7. Conclusions
8. Literature & Links

1. Introduction

We will implement a recursive version to generate the permutations of a string literal. In discrete mathematics, specifically in counting techniques, a key topic is permutations: a permutation lets the programmer to count elements of a given set of a domain model. Given that, permutations has a great number of applications in computer science.

2. Keywords

• Computer science
• Counting
• Discrete mathematics
• Model
• Permutation

3. Problem

Generate permutations for the characters of a string literal.

4. Solution

An algorithm, in LINQ, will be implemented to generate partial permutations, and to generate all possible permutations.

5. Discussion

5.1 Permutations

In the context of mathematics, a permutation consists in the arrangement of elements of a set. For example, the list of numbers {1, 2, 3} has these six permutations (without repetition): 

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 1), and (3, 2, 1).

In the same way, if we assign red to 1, green to 2, and blue to 3, we also have these six permutations ("Permutation [Wikipedia]", 2016): 

Illustration 1. Color permutations ("Permutation [Wikipedia]", 2016).

How do we calculate the number of permutations? It's easy: we must compute the factorial of the n elements in the set: 

6. Practice: Generating Permutations

For this LINQ recipe we are going to use LINQPad in C# Program mode: 

Illustration 2. LINQPad in C# Program mode.

Our code solution is implemented using C# programming language and LINQ standard query operators: 

LINQ file Permutations.linq [Alternative link][Alternative link]:

Method GeneratePartialPermutation(string) (lines 2-6) performs the following operations: 

• Lines 4-5: Creates a HashSet of string objects with partial permutations. If the string "abcd" is passed, it produces "abcd", "bacd", "cabd" and "dabc". These permutations are rotated versions of the given string object: each character is brung to the front and the others remain unchanged.

In the Main method these expressions are processed: 

• Line 13: Method GeneratePartialPermutation() is invoked to generate the first permutations for "abcd"; i.e., "abcd", "bacd", "cabd" and "dabc".
• Lines 17-45: Ensures that all possible permutations are generated.
• Lines 24-32: Partial permutations generated in line 13 are processed.
• Lines 35-43: Partial permutations generated in line 13 are processed in reverse order.

A test execution for this LINQ recipe is presented: 

7. Conclusions

Our implementation in section 6 has allowed us to understand a functional programming approach to generate permutations. We have also understood that permutations is a counting technique in discrete mathematics.

The next recipe will teach us how to generate a power set.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Combinations and Permutations (2016, July 4). Retrieved from: https://www.mathsisfun.com/combinatorics/combinations-permutations.html
Permutation (2016, July 4). Retrieved from: http://mathworld.wolfram.com/Permutation.html
Permutation (2016, July 4). Retrieved from: https://en.wikipedia.org/wiki/Permutation

V

LINQ Recipe No. 2-13: How to Generate Fibonacci Numbers Nonrecursively

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 Fibonacci numbers
5.2 Nonrecursive way to compute Fibonacci numbers
6. Practice: Fibonacci Numbers Generation
7. Conclusions
8. Literature & Links

1. Introduction

Functional programming with LINQ is amazing! In this new LINQ recipe we will be to able to compute Fibonacci numbers in a non-recursive fashion. For this, as we will see soon, we just only need to sum up the last previous numbers.

2. Keywords

• Fibonacci
• Functional programming
• Recursivity

3. Problem

Generate Fibonacci numbers using a nonrecursive algorithm.

4. Solution

LINQ allows us to implement an alternative way to compute Fibonacci numbers just using a generator function, and then apply a simple lambda expression over these numbers with the ForEach method from List<T> generic collection.

5. Discussion

5.1 Fibonacci numbers

The Fibonacci serie is sequence of integer positive values. These numbers are defined by the recursive relation ("Fibonacci number", 2016): 

and these are the base cases or seed values: 

For example: 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

There are a lot of interesting mathematical facts which are based on this recursive relation; for example: 

• Divisibility properties, 
• Fibonacci primes, 
• Periodicity modulo n, 
• Primality testing

But this series is also expressed in nature: the length of the algae string is at each growth stage is equal to Fibonacci numbers.

But...

5.2 Nonrecursive way to compute Fibonacci numbers

With LINQ we can implement this series using a much faster algorithm: we just need to compute the sum of the last two numbers: this can be accomplished just only using a list data structure to recover the last computed two numbers in the series.

6. Practice: Fibonacci Numbers Generation

In the first place, we must remember that recursion implementations are stateless; this means, in other words, that recursive algorithms are forgetful (Mukherjee, 2014). With this in mind, we need to use a data structure to maintain the computed Fibonacci numbers.

Under that requirement, this is the implementation in LINQ: 

LINQ file NonRecursiveFibonacci.linq [Alternative link][Alternative link]: 

In line 2 we declare and create a List with the parametric type ulong. This will serve us as the data structure to store the computed Fibonacci numbers.

Then, the code defined in lines 6-10 performs these operations: 

• Line 6: Creates a range of integer values from 0 to 200.
• Line 7: Converts the range into a List.
• Lines 8-10: This code computes the Fibonacci numbers following these simple rules: 
• If the given number k is less or equal to 1, the number 1 is added to the list.
• On the contrary, if the previous condition is not met, then the sum of last two numbers in the list are computed.

Finally, the first 53 Fibonacci numbers are shown in the output (line 13).

In this video tutorial an explanation is given to this process: 

7. Conclusions

We have explored a new way to generate Fibonacci numbers: this alternative implementation avoids, eventually, an overflow, and takes less time.

LINQ recipe no. 2-14 will teach us how to generate permutations.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Fibonacci number (2016, July 4). Retrieved from: https://en.wikipedia.org/wiki/Fibonacci_number

V