Sequences and Lists Processing

The objective of this tutorial is to refresh and reinforce some of the basic notions in sequence and list processing which is fundamental for the development of advanced computational designs. The assumptions include basic understanding of the C# programming language and structural concepts from the Introduction to Computation course.

Sequence Generation

The code below generates a sequence of numbers from 0 to count – 1. It is recommended that the number of elements is defined as count prior to the for-loop construct and the iterated element variable (or subscript) is named as index.

List Generation

Lists are a special kind of linear collections of data that dynamically expand when a new element is placed as the end of the sequence using the Add method. Lists are typically uniform in the type of elements they contain such as int, double, string etc. A list of type object however can be used to store any kind of information because all types are related to the object type.

Note that the term List<Type> used in the declaration and initialization is also a unique type of data in itself in as much as int, double or string. Therefore types can nest in more complex types. Also the type List<Type> is descendant of type object. Therefore we can store any list inside an object typed variable or even a list of objects. This composition of types and values is what make programming expressive and allows complex concepts to be represented by simple numbers that computers understand.

Combine Lists

It is possible to combine two lists together by placing all element of one into another. Below are to methods to perform this kind of composition. This is also to demonstrate the AddRange method supported by .NET lists.

Reversing a List

The following procedure demonstrates how to reverse the elements of a list. First we will use a temporary list to achieve this and then we will use the Reverse method supported by .NET lists. You can try to reverse a list in place. It is a tricky but not that tricky algorithm.

Remove Element from List

Lists can also contract using the Remove or RemoveAt methods, not only expand using Add or AddRange.

Arrays of Numbers

Arrays are also linear containers accessed by index like lists but they have fixed size by definition. They are simpler data collections, closer to hardware, faster but are also less flexible. While most computing textbooks put more emphasis on arrays, as being more fundamental, it makes sense to use lists as being more general purpose. Below is the same example as above only with array notation.

Notice that arrays are automatically filled with the number of elements expressed in the declaration + initialization. The value of all 32 elements will be automatically assigned using the default value for the specific type of element. For numbers the default value is zero and for complex types generally is null (undefined). This means that array elements are immediately accessible before adding them into the container or assigning anything to them for the first time. Remember lists need to be filled with Add before being able to read and write their elements.

Sequence of Random Numbers

The following procedure demonstrates the creation of a list containing random real numbers from 0.0 to 1.0. Read more about the class System.Random in Microsoft Developer Network (just Google: System.Random). There are other methods for initializing the pseudo random number generator (PRNG) or extracting integers.

Translation of a Sequence

To translate a sequence we create a new list and for-each element of the previously create list we add an offset value. It is recommended that you imagine lists geometrically as a chain of points on the real line rather than numbers in spreadsheet boxes. Translation shifts the point collection forward or backward based on the offset. In conclusion, addition and subtraction of sequences can be geometrically thought of as translation.

Lists apart from the elements also store one more bit of information which is the number thereof. This information can be accessed through the read only property Count. In addition, the elements of a list can be accessed both for reading and writing using the square bracket [index] notation seen below.

Scaling a Sequence

Scaling a sequence is equivalent to multiplication of each element by a factor. Geometrically we are spreading the point collection uniformly apart. Another way to visualize the operation is by thinking a sequence as a line segment. A line that starts from 0 to n-1 scaled by a factor s will remain starting from o but its end-point will end up at s * (n – 1). On the other hand a sequence starting from 5 to 10 will have both its start and end points translated by the operation of scaling.  In conclusion, multiplication and division of sequences can be geometrically thought of as scaling.

Normalizing a Sequence

Normalization is the process of transforming a sequence from an arbitrary range to the unit range. This is most often performed by dividing the sequence by its largest element. The objective of this operation is to simplify the information contained in the sequence by removing the magnitude information which becomes always one. Another way to think about it is that normalization removes the implied units of the quantities stored (assume we store meters) and transforms the sequence to proportions (assume percentages).

Compute the Average Value

In order to compute the average value of the items in a list you need to create an auxiliary variable to store the sum (also known as accumulator) and at the end of the summation divide with the number of elements. Notice how simple is to translate mathematical summations Σ and products Π into code. Now, finding the median value within a list is a rather tricky algorithm!

Counting the Number of Occurrences

The following example demonstrates how to count the number of occurrences of a value in a list by exhaustive enumeration, comparison and counting.

Clip Values below Threshold

The following procedure eliminates all negative values, by setting their value to zero, from a list for which we only know it contains real numbers.

Force Values in Range

This is an extension to the previous procedure where by we aim to clip values outside a specified range. Again we assume that we have a list of numbers.

Find and Replace all Elements

The following example finds and replaces all instances of a value with another. It is easy to modify the code below to replace only the first instance if found.

Finding an Element in a List

Search is very common procedure in list processing. The following code demonstrates how to find a predefined element value by looking incrementally (by comparison) through every element of the list. Upon the first occurrence of the element in the list, the iterated procedure exits the loop and reports its result. If the element does not exist in the list then by the end of the loop the location value will be negative as it was initialized. This invalid value for list index  (lists can be indexed from 0 to Count – 1) is used to signal the absence of the value searched for.

This is common convention used by many programming languages and libraries associated with them. In fact the type List comes with predefined methods one of which is IndexOf. Said function finds the first occurrence of the specified value or negative one otherwise. Because this procedure may take at most equal steps as the maximum number of elements in the list, it often called Linear Search with worst case time complexity O(n).

Find the Maximum Value in a List

The following procedure finds the maximum (or minimum with small changes) element in a list. The logic is quite simple: Look through every element and each time there is a smaller one than what has been seen so far, store its location and value. To kick start the procedure we need to initialize the location and value of the best maximum found to something invalid and/or trivially overwritable by the first iteration of the loop logic. In the example we use a super small value for initial guess and negative one for its location. If the list is empty we will know that the maximum value is invalid as its index is negative. The procedure may take as many iterations as the number of elements in the list so it is therefore linear O(n) the size of the list. For practice write the equivalent algorithm to find the minimum value.

Generate a Grid of Elements

A grid (or matrix) is a 2D dimensional construct of elements which is captured computationally by a nested pair of loops as seen below. Notice that conceptually the external loop runs over rows and the internal over columns.

Store a Grid using List of Lists

There are many approaches to storing 2D data. Keeping in with the list argument used so far we will declare and initialize a list of lists (perhaps a list of row lists) and then use the construction above to store the elements. Notice that we literally create a list of lists by instantiating a new row each iteration, we fill it with strings in the interior loop and eventually store the whole row into the grid list. To extract elements from the list we use the two subscript form list[i][j]. To extract a whole row we can use list[i] (think of it as calling a function that takes in an index and returns a list). The interior lists need not be the same size!

 Generate All Pairs of Elements

Often it is useful to process all the pairs of the elements of a list. This is best visualized as a square matrix where we want to keep only the item above or below the diagonal (with the diagonal items). Since this is a 2D operation we need two nested loops but the initial and end values are carefully selected so we avoid self-pairing or duplication.

Since we will look forward one item to pair it with the neighbor the exterior loop needs to stop one element before the last (otherwise we will get an out of bounds exception). The interior loop will need to start one element ahead of the exterior loop index to avoid self-pairing and move all the way to the end.

Print a Grid of Elements

Assuming we have a list of lists with no additional information about the content we will print them in a matrix form using the logic seen below. Notice that as lists can expand (and contract) we can assume that all sub-lists will have the same number of elements.

Scanline Access of Lists

The nested loop construct for accessing lists creates a unique zig-zag pattern of access if we observe the order of the elements visited. In the following example we print the two-subscript index (i,  j) along with a linear path index (k)

Sort a List of Numbers

Assuming the list contains an unknown number of elements in random order we will reorder them in ascending or descending fashion using the following super simple algorithm. The particular implementation is easy to remember and quite useful for small collections but it is considered as suboptimal because at worst case it can take O(n^2) iterations as opposed to O(nlogn) which is considered the best when using comparisons and swaps.

Anyways, the insight into what is going on is this: We look for the largest/smallest element in the list using the linear search strategy and replace it with the one in the front of the list. We then know that we are done with it and thus can assume we have a smaller list to sort with one less element. So we repeat the same logic getting done element by element from the front to the end of the list.

Shuffle the Elements of a List

To create a list of randomly chosen values it is not advisable to use the random number generator to directly extract indices from the list. This is because the PRNG may produce duplicates. Shuffling on the other hand retains the identity of the elements by swapping pairs randomly. The following is a very simple implementation of shuffling. See Fisher-Yates for a marginally more complex but more random shuffling algorithm.

Unfolding a List of Lists into a List

The following example demonstrates how to convert between a two dimensional list of lists to a linear list. The transform from ( i, j ) → ( index ) = ( i * m + j ) where m is the number of rows of the grid.

Folding a List into a List of Lists

The following example demonstrates how to convert between a one dimensional list and two dimensional list of lists. Notice that we use integer division to determine the map from ( index ) → ( i,  j ) = ( index / m, index % m ) where m is the number of rows of the grid.