Algorithms For Dummies. John Paul Mueller
Shuffling combinations
In some cases, you don't need an entire dataset; all you really need are a few of the members in combinations of a specific length. For example, you might have a dataset containing four numbers and want only two-number combinations from it. (The ability to obtain parts of a dataset is a key function for generating a fully connected graph, which is described in Part 3 of the book.) The following code shows how to obtain such combinations:
from itertools import combinations a = np.array([1,2,3,4]) for comb in combinations(a, 2): print(comb)
which produces this output:
(1, 2)(1, 3)(1, 4)(2, 3)(2, 4)(3, 4)
The output contains all the possible two-number combinations of a. Note that this example uses the itertools combinations() function (the permutations() function appears in the previous section). Of course, you might not need all those combinations; perhaps a random subset of them would work better. In this case, you can rely on the random.sample() function to come to your aid, as shown here:
import random pool = [] for comb in combinations(a, 2): pool.append(comb) print(random.sample(pool, 3))
The precise combinations you see as output will vary, such as [(1, 2), (2, 3), (1, 4)]. However, the idea is that you've limited your dataset in two ways. First, you’re not using all the data elements all the time, and second, you’re not using all the possible combinations of those data elements. The effect is to create a relatively random-looking set of data elements that you can use as input to an algorithm. Python provides a whole host of randomizing methods that you can see at https://docs.python.org/3/library/random.html. Many of the later examples in this book also rely on randomization to help obtain the correct output from algorithms.
Facing repetitions
Repeated data can unfairly weight the output of an algorithm so that you get inaccurate results. Sometimes you need unique values to determine the outcome of a data manipulation. Fortunately, Python makes it easy to remove certain types of repeated data. Consider this example:
a = np.array([1,2,3,4,5,6,6,7,7,1,2,3])b = np.array(list(set(a))) print(b)
The output contains only the unique elements:
[1, 2, 3, 4, 5, 6, 7]
a begins with an assortment of numbers in no particular order and with plenty of repetitions. In Python, a set never contains repeated data. Consequently, by converting the list in a to a set and then back to a list, and then placing that list in an array, you obtain a vector that has no repeats.
Getting the Desired Results Using Recursion
Recursion, an elegant method of solving many computer problems, relies on the capability of a function to continue calling itself until it satisfies a particular condition. The term recursion actually comes from the Latin verb recurrere, which means to run back.
When you use recursion, you solve a problem by calling the same function multiple times but modifying the terms under which you call it. The main reason for using recursion is that it provides an easier way to solve problems when working with some algorithms because it mimics the way a human would solve it. Unfortunately, recursion is not an easy tool because it requires some effort to understand how to build a recursive routine, and it can cause out-of-memory problems on your computer if you don't set some memory settings. The following sections detail how recursion works and give you an example of how recursion works in Python.
Explaining recursion
Many people have a problem using recursion because they can’t easily visualize how it works. In most cases, you call a Python function, it does something, and then it stops. However, in recursion, you call a Python function, it does something, and then it calls itself repeatedly until the task reaches a specific condition — but all those previous calls are still active. The calls unwind themselves one at a time until the first call finally ends with the correct answer, and this unwinding process is where most people encounter a problem. Figure 4-1 shows how recursion looks when using a flow chart.
Notice the conditional in the center. To make recursion work, the function must have such a conditional or it could become an endless loop. The conditional determines one of two things:
The conditions for ending recursion haven’t been met, so the function must call itself again.
The conditions for ending recursion have been met, so the function returns a final value that is used to calculate the ending result.
FIGURE 4-1: In the recursion process, a function continuously calls itself until it meets a condition.
One of the most common examples of recursion for all programming languages is the calculation of a factorial. A factorial is the multiplication of a series of numbers between a starting point and an ending point in which each number in the series is one less than the number before it. For example, to calculate 5! (read as five factorial), you multiple 5 * 4 * 3 * 2 * 1. The calculation represents a perfect and simple example of recursion. Here’s the Python code you can use to perform the calculation.
def factorial(n): print("factorial called with n = ", str(n)) if n == 1 or n == 0: print("Ending condition met.") return 1 else: return n * factorial(n-1) print(factorial(5))
Here is the output you see when running this example:
factorial called with n = 5factorial called with n = 4factorial called with n = 3factorial called with n = 2factorial called with n = 1Ending condition met.120
The code meets the ending condition when n == 1. Each successive call to factorial() uses factorial(n-1), which reduces the starting argument by 1. The output shows each successive call to factorial and the meeting of the final condition. The result, 120, equals 5! (five factorial).
It's important to realize that there isn’t just one method for using recursion to solve a problem. As with any other programming technique, you can find all sorts of ways to accomplish the same thing. For example, here’s another version of the factorial recursion that uses fewer lines of code but effectively performs the same task:
def factorial(n): print("factorial called with n = ", str(n)) if n > 1: return n * factorial(n-1) print("Ending condition met.") return 1 print(factorial(5))