# 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.

``````//-- Define the Number of Elements
//--
var count = 32;

//-- Generate and Emit Elements
//--
for( var index = 0; index < count; index++ )
{
Print( "Element " + 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.

``````//-- Create a new List of Integers
//--
var list = new List<int>( );

//-- Define the Number of Elements
//--
var count = 32;

//-- Generate and Store Elements
//--
for( var index = 0; index < count; index++ )
{
}

//-- Get the Number of Elements
//--
var size = list.Count;

//-- Extract an Element from List by Index
//--
var first  = list;
var second = list;
var third  = list;
var last   = list[list.Count - 1];
//-- Assign Element by Index
//--
list[             0] = 9; //-- Set First
list[             4] = 6; //-- Set Fifth
list[list.Count - 1] = 1; //-- Set Last

//-- Index Out of Bounds Exceptions
//-- (index must be >= 0 and < Count)
list[-1] = 1;
list = 2;

//-- Create and Fill a List
//--
list = new List<int>( ) { 0, 1, 2, 3 };``````

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.

```var list_a = new List<int>( ) { 1, 2, 3, 4 };
var list_b = new List<int>( ) { 4, 5, 6 };

//-- Merging Lists Manually
//--
for( var index = 0; index < list_b.Count; index++ )
{
}

//--
```

## 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.

```var list = new List<int> { 1, 2, 3, 4 };

//-- Using Temporary Storage
//--
var temp = new List<int>( );

for( var index = list.Count - 1; index >= 0; index-- )
{
}

list = temp;

//-- Using Reverse Method
//--
list.Reverse( );
```

## Remove Element from List

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

```var list = List<int>( ) { 1, 2, 3, 4, 5 };

//-- Remove by Value
//--
list.Remove( 2 );

//-- Remove by Index
//--
list.RemoveAt( 0 ); //-- aka Remove First```

## 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.

``````//-- Create an Array
//--
var count = 32;
var array = new int[count];

//-- Store Data
//--
for( var index = 0; index < count; index++ )
{
array[index] = index;
}

//-- Number of Elements
//--
var size = array.Length;

//-- Extract Element
//--
var second = array;

//-- Assign Element
//--
array[array.Length - 1] = 1000;
``````

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.

``````//-- Create Random Number Generator
//--
var random = new System.Random( );

//-- Generate List of Random Numbers
//--
var list = new List<double>( );

var count = 32;
for( var index = 0; index < count; index++ )
{
}``````

## 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.

``````//-- A1. Create a new List of Integers
//--
var output = new List<int>( );

//-- A2. Translate the Elements by Offset 5
//--
for( var index = 0; index < list.Count; index++ )
{
}

//-- B1. In Place Translation
//--
for( var index = 0; index < list.Count; index++ )
{
list[index] = list[index] - 10; // or list[index] -= 10;
}
``````

## 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.

``````//-- In Place Scaling (Doubling)
//--
for( var index = 0; index < list.Count; index++ )
{
list[index]  = list[index] * 2;

//list[index] *= 2;                 //-- Same result
//list[index] += list[index];       //-- Alternative
}``````

## 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).

``````//-- Create List Storage
//--
var list = new List<int>( );

//-- Generate 0..Count-1
//--
var count = 32;
for( var index = 0; index < list.Count; index++ )
{
}

//-- Scale to 0..1 Range
//--
for( var index = 0; index < count; index++ )
{
list[index] = index / ( count - 1 );
}``````

## 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!

``````//-- Initialize Accumulator
//--
var average = 0.0;

//-- Perform Summation
//--
for( var index = 0; index < count; index++ )
{
average += list[index];
}

//-- Scale by Number of Elements
//--
average /= list.Count;``````

## 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.

``````var list = new List<int>( ) { 2, 3, 1, 5, 8, 2, 8, 1, 4, 8 };

var match = 8;
var times = 0;

for( var index = 0; index < list.Count; index++ )
{
if( list[index] == match )
{
++times;

Print( "Found @" + index );
}
}

Print( "Item: " + match + " Found: x" + times );``````

## 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.

```for( var index = 0; index < list.Count; index++ )
{
if( list[index] < 0.0 )
{
list[index] = 0.0;
}
}```

## 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.

```var min = 0.0;
var max = 1.0;

for( var index = 0; index < list.Count; index++ )
{
if( list[index] < min ) list[index] = min; else
if( list[index] > max ) list[index] = max;
}```

## 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.

``````var list = new List<int>( ) { 2, 3, 1, 5, 8, 2, 8, 1, 4, 8 };

var find = 2;
var swap = 9;

for( var index = 0; index < list.Count; index++ )
{
if( list[index] == find )
{
list[index] = swap;
}
}``````

## 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).

``````var look_for =  5; //-- Element Value to Search For
var location = -1; //-- Location of Element Found

//-- Look in List for Every Element
//--
for( var index = 0; index < list.Count; index++ )
{
//-- If Found Exit the Loop
//--
if( list[index] == look_for )
{
location = index;
break;
}
}

//-- Report Result
//--
if( location < 0 )
else
Print( "Found " + look_for + " at " + location );``````

## 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.

``````var max_value = -1000000;  //-- Assume something super small eg. int.MinValue or double.MinValue
var max_index = -1;        //-- Assume something invalid as kind of a sentinel marker

for( var index = 0; index < list.Count; index++ )
{
//-- Is Current Value Bigger?
//--
if( list[index] > max_value )
{
//-- Lets update then
//--
max_value = list[index];
max_index = index;
}
}

Print( "Maximum Value is " + max_value + " at " + max_index );```
```

## 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.

``````var n = 3;
var m = 4;

for( var i = 0; i < n; i++ )
{
for( var j = 0; j < m; j++ )
{
Print( "i: " + i + " j: " + j );
}
}``````

## 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!

``````//-- Declare List of ( List of ( string ) )
//-- and Create a new instance
//--
var grid = new List<List<string>>( );

var n = 3;
var m = 5;

//-- Store Elements
//--
for( var i = 0; i < n; i++ )
{
var row = new List<string>( );
for( var j = 0; j < m; j++ )
{
row.Add( "(" + i + "," + j + ")" );
}
grid[i] = row;
}

//-- Print All Elements
//--
for( var i = 0; i < n; i++ )
{
for( var j = 0; j < m; j++ )
{
Print( grid[i][j] );
}
}

//-- Create and Fill a List of Lists
//--
var mat4x4 = new List<List<int>>( )
{
new List<int>( ) { 1, 0, 0, 0 },
new List<int>( ) { 0, 1, 0, 0 },
new List<int>( ) { 0, 0, 1, 0 },
new List<int>( ) { 0, 0, 0, 1 }
};

//-- Create and Fill a List of Lists 2
//--
var tris = new List<List<int>>( )
{
new List<int>( ) { 0, 1, 2 },
new List<int>( ) { 0, 1 },
new List<int>( ) { 0 }
};
``````

# 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.

``````var n = list.Count;

//-- No need for the last
//--
for( var i = 0; i < n - 1; i++ )
{
//-- From the next forward!
//--
for( var j = i + 1; j < n; j++ )
{
Print( "(" + i + "," + j + ")" );
}
}
``````

## 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.

``````var n = list.Count;
for( var i = 0; i < n; i++ )
{
var m = list[i].Count;
for( var j = 0; j < m; j++ )
{
Print( "(" + i + "," + j + ") -> " + list[i][j] );
}
}``````

## 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)

``````var k = 0;

var n = list.Count;
for( var i = 0; i < n; i++ )
{
var m = list[i].Count;
for( var j = 0; j < m; j++ )
{
Print( "(" + i + "," + j + ") -> " + k + " = " + list[i][j] );
++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.

``````var n = list.Count;

//-- Remember we go up to n - 1
//--
for( var i = 0; i < n - 1; i++ )
{
//-- Remember we start from i + 1
//--
for( var j = i + 1; j < n; j++ )
{
if( list[i] < list[j] )
{
//-- Swap value using temporary variable
//--
var tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}
}``````

## 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.

``````var random = new System.Random( );

for( var i = 0; i < list.Count; i++ )
{
//-- Pick Randomly
//--
var j = random.Next( list.Count );

//-- Swap Places
//--
var tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}``````

## 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.

``````//-- Declare, Create and Fill a List of Lists
//--
var grid = new List<List<int>>( )
{
new List<int>( ) { 11, 21, 31, 41 },
new List<int>( ) { 12, 22, 32, 42 },
new List<int>( ) { 13, 23, 33, 43 }
};

//-- Declare, Create and Fill a List
//--
var line = new List<int>( )
{
0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0
};

//--
var n = grid.Count;
for( var i = 0; i < n; i++ )
{
var m = grid[i].Count;
for( var j = 0; j < m; j++ )
{
line[i * m + j] = grid[i][j];
}
}

for( var index = 0; index < line.Count; index++ )
{
Print( "i: " + i + " -> " + line[i] );
}
``````

## 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.

``````//-- Declare, Create and Fill a List
//--
var line = new List<int>( )
{
1, 2, 3,  4,  5,  6,
7, 8, 9, 10, 11, 12
};

//-- Declare, Create and Fill a List of Lists
//--
var grid = new List<List<int>>( )
{
new List<int>( ) { 0, 0, 0, 0 },
new List<int>( ) { 0, 0, 0, 0 },
new List<int>( ) { 0, 0, 0, 0 }
};

for( var index = 0; index < line.Count; index++ )
{
var i = index / 3;
var j = index % 3;

grid[i][j] = line[index];
}

var n = grid.Count;
for( var i = 0; i < n; i++ )
{
var m = grid[i].Count;
for( var j = 0; j < m; j++ )
{
Print( "i: " + i + " j: " + j + " -> " + grid[i][j] );
}
}``````