Tag Archives: list

One of the somewhat unforeseen consequences of taking a career in applied mathematics, particularly in this day and age, is that you will eventually need to write computer programs that implement the mathematical algorithms. There are several languages in which one can do this, each with its own positives and negatives and you will find that things that are simple in some are difficult in another. After speaking with a number of people, both students and professionals who work with mathematics on a regular basis, I reasoned that it may be helpful to provide some source code examples to help mathematicians get started with programming in some of these languages. I decided to start with Python because its a powerful language, available for free, and its learning curve isn’t too steep.

I will be working with Python 2.7, which can be downloaded from https://www.python.org/download/releases/2.7/. I understand, however, that a limitation to coding is the required setup often necessary before one can even write their first line of code. So while I do encourage you to download Python, I will also provide a link to the online Python compiler at Compile Online, which should allow users to simply copy and paste the code into a new tab in their browser and by simply clicking the “Execute Script” command in the upper left corner, see the output of the code.

With that being said, here is a link to my sample Python code.

Blog, Examples

Permutation Problems

May 13, 2013 AfterMath Leave a comment

I love to play with puzzles. When I was in grade school I would spend hours at a time figuring out ways to solve from things like Tetris, Mindsweeper, Solitare, and Freecell. Later I was introduced to puzzles involving numbers like Sudoku and Nonograms.

These puzzles are often interesting in part because there is generally a very large way that things can be arranged, but only a few of these arrangements are correct. Generally a person solving a puzzle will figure out certain things that must be true or cannot be true, which helps in solving the puzzle and reducing the number of possible cases. Initially, though, we are often left with a situation where we have a new puzzle and our only method is to keep trying every possible solution until we start to notice a pattern (or reach a solution).

For example, consider a Sudoku puzzle. We are given a partially filled in grid and our job is to fill in the remaining cells with the rules that every row, column and marked subgrid must have the numbers 1 – 9 exactly once. One initial attempt at solving such a puzzle could be to attempt to permute the string 1, 2, 3, 4, 5, 6, 7, 8, 9 until we find a solution that fits the first row, then do the same with the second row, and so on and so forth.

One immediate question is how many ways are there to permute the numbers 1, …, 9? We can answer this by realizing that each permutation is a new string. So for each string that we construct, we have 9 choices for the first element in the string. Then once that element has been chosen, we are not allowed for that element to appear anywhere else. So there are only 8 possible choices for what can go in the second string. Continuing this process, we see that the number of possible permutations we can construct from the string 1, …, 9 is

9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880

This is a large number of possible strings to generate just to get one row of a Sudoku, so hopefully you’ll be able to notice the pattern before going through this whole set (because once you’ve generated the first row you still have to do the other 8 rows).

Nonetheless because there is often great value that can be gained by knowing how to permute through all possible solutions, I have written three functions that help with this process: Next_Permutation, Previous_Permutation, and Random_Permutation.

Before I give these algorithms, I want to highlight two notations on ordering string. A string (a₁, a₂, …, a_n) is said to be in lexicographical order (or alphabetical order) if for each i [in] 1, …, n-1, a_i [<=] a_i+1. Likewise, a string is said to be in reverse lexicographical order if for each i [in] 1, …, n-1, a_i [>=] a_i+1.

Next Permutation

If the given string is not in reverse lexicographic order, then there exists two elements j₁ and j₂ such that j₁ [<] j₂ and a_j₁ [<] a_j₂.
1. The Next_Permutation algorithm first searches for the largest element j₁ such that a_j₁ [<] a_{j₁ + 1}. Since we said the string is not in reverse lexicographic order, this j₁ must exist.
2. Once this j₁ is found, we search for the smallest element a_j₂ such that a_j₂ [>] a_j₁. Again, since we know that this is true for j₁ + 1, we know that such a j₂ must exist.
3. We swap the elements a_j₁ and a_j2.
4. The elements after j₁ + 1 are then placed in lexicographic order (i.e. in order such that a_i [>=] a_i+1

If the given string is in reverse lexicographic order, then we simply reverse the string.

Previous Permutation

If the given string is not in lexicographic order, then there exists two elements j₁ and j₂ such that j₁ [<] j₂ and a_j₁ [>] a_j₂.
1. The Previous_Permutation algorithm first searches for the largest element j₁ such that a_j₁ [>] a_{j₁ + 1}. Since we said the string is not in reverse lexicographic order, this j₁ must exist.
2. Once this j₁ is found, we search for the smallest element a_j₂ such that a_j₁ [>] a_j₂. Again, since we know that this is true for j₁ + 1, we know that such a j₂ must exist.
3. We swap the elements a_j₁ and a_j2.
4. The elements after j₁ + 1 are then placed in reverse lexicographic order (i.e. in order such that a_i [<=] a_i+1

If the given string is in lexicographic order, then we simply reverse the string.

Random Permutation

This generates a random string permutation.

This script can be seen here, set to work on permutations of colors.

Blog, Examples

Nonogram Puzzles

February 8, 2013 AfterMath 3 Comments

A friend introduced me to a type of puzzles called Nonograms and I enjoyed them so much that I wrote a script that automatically generates these puzzles.

Nonograms are grid puzzles based on discovering the hidden pattern based on the clues provided. This hidden pattern is the answer to the question of which cells of this grid should be shaded black, and which ones should be shaded grey. The clues come in the form of lists at the beginning of each row and column. The list represents the sizes and order of the groups of shaded cells in that line. For example, if there is a list with the numbers “4 2”, then it says that the group has 4 shaded cells, then one or more unshaded cell, then two shaded cells. Because 4 becomes before 2 in the list, the 4 shaded cells would become before the 2 shaded cells in the line of the grid. Also there must be at least one unshaded cell in between the groups because if there wasn’t, then the “4 2” list would actually be a group of 6 shaded cells.

So have fun with these and let me know what you think.

Other Blogs that have covered this topic:
MINIGAMESCLUB

Blog, Examples

Arithmetic Sequences

February 2, 2013 AfterMath Leave a comment

I’ve added a script which helps to understand arithmetic sequences.

At a previous job of mine, there was a policy of holding a dinner party for the company each time we hired a new employee. At these dinners, each employee was treated to a $20 dinner at the expense of the company. There was also a manager responsible for keeping track of the costs of these dinners.

In computing the costs, the manager noticed that each time there is a new dinner, it was $20 more expensive than the last one. So if we let a₁ represent the cost of the first dinner, and let a_i represent the cost of the i^th dinner, then we see that a_i = a_i-1 + 20. Sequences like this, where t arise quite often in practice and are called arithmetic sequences. An arithmetic sequence is a list of numbers where the difference between any two consecutive numbers is constant.

For the example above, the term a_n will represent the cost of dinner after the n^th employee has joined the company (assuming that no employees have left the company over this time period). Also the term S_n will represent the total cost the company has paid towards these dinners.

Before we continue with this example, consider the following table which lists the first five terms of an arithmetic sequence as well as the common difference and the first five sums of this sequence.

term number	term value	diff	sum number	sum value
a₁	4	3	S₁	4
a₂	7	3	S₂	11
a₃	10	3	S₃	21
a₄	13	3	S₄	34
a₅	16	3	S₅	50

One of the beauties of arithmetic sequences is that if we know the first term (a₁) and the common difference (d), then we can easily calculate the terms a_n and S_n for any n with the following formulas:

a_n = a₁ + d*(n – 1), where d is the common difference.
S_n = n*(a₁ + a_n)/2

We can use these formulas to derive more information about the sequence. For example, if my manager wanted to estimate the cost of dinners once we had added 30 new employees, this would be term a₃₀ of the sequence, which we can evaluate with the above formula by a₃₀ = a₁ + d*(n – 1) = 0 + 20*(30 – 1) = 0 + 20 * 29 = 580.

The script is available at http://www.learninglover.com/examples.php?id=33.

Other Blogs that have covered this topic:
Study Math Online

Blog, Examples

Examples of the Binary Search Algorithm

June 25, 2012 AfterMath Leave a comment

I have published code that shows examples of the Binary Search Algorithm.

In order for this algorithm to be applicable, we need to assume that we’re dealing with a sorted list to start. As a result, instead of proceeding iteratively through each item in the list, the binary search algorithm continually divides the list into two halves and searches each half for the element.

It can be shown that the maximum number of iterations this algorithm requires is equivalent to the number of times that we need to divide the list into halves. This is equivalent to a maximum number of iterations along the order of log₂(n), where n is the number of items in the list.

A collection of scripts to help users gain a love of mathematics, computer science, probability and how they interact with the world around us.