Many computational problems can be solved by trying all possible candidate solutions until the correct solution to the problem is found. This approach is often called Exhaustive Search or Brute Force Search. Although clumsy and inefficient, exhaustive search is often well worth implementing to get a feel for a problem before trying to implement a better solution.
The reason a better solution if often needed is that for many problems, the brute force method takes an impractical amount of time to solve. This can often mean ridiculous amounts of time such as around 585 billion years to solve the famous Towers of Hanoi Puzzle with just 64 rings, if each move took one second.
Remember the computer that had to work out the answer to life the universe and everything and eventually came up with 42? (If not, I thoroughly recommend getting you hands of a copy of the book “The Hitchhikers Guide to the Galaxy”…)
Algorithmic Thinking with Python
If you want to learn more about algorithmic thinking with Python check out my course on LinkedIN Learning.
Algorithmic Thinking with Python Video Course
Let’s look at some examples of brute force algorithms in Python.
Python Brute Force Algorithms
Imagine you have been asked to find all the even numbers up to 100 using Python. How would you do it? As is usually the case there is more than one way to solve this problem. For now though, don’t worry about coming up with anything but the most obvious approach.
In order not to spoil you fun, I will hide my brute force solution to this problem. Click below to reveal it.
If you used a different approach that is absolutely fine. My version is just a way to illustrate what a brute force approach might look like. Can you see how my version involved going through every possible candidate and checking for evenness?
Linear search in Python
Another classic example of a brute force algorithm is Linear Search. This involves checking each item in a collection to see if it is the one we are looking for.
In Python, it can be implemented like this:
def linear_search(haystack, needle):
for position, item in enumerate(haystack):
if item == needle:
return position
return -1
print(linear_search([4, 5, 2, 7, 1, 8], 7))
Of course there are many different implementations of this algorithm. I like this one because it makes use of Python’s very handy enumerate function. Regardless of the details of the implementation, the basic idea remains the same – iterate through the collection (in the case above, a Python list), and check if each item is the target. I like to use the variable names needle and haystack from the expression looking for a needle in a haystack.
Bubble Sort in Python
A common algorithm in Computer Science courses is Bubble Sort. It is a useful learning tool, though of little practical value. The main reason for this is its brute force approach. We use nested for loops, that is a for loop within another for loop, to make every possible comparison and swap if necessary until the data is sorted.
As with linear search, there are many variations in how Bubble Sort is implemented, but the essential idea remains the same. You can read more about Bubble Sort here.
Here is an example Python implementation of Bubble Sort:
# Python implementation of Bubble Sort
def bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# Traverse the array from 0 to n-i-1
# If the element found is greater than the next element, swap
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)
arr = [3, 8, 2, 5, 6, 1, 9, 4, 7]
bubble_sort(arr)
print("Sorted array is:", arr)
Above are three examples of brute force algorithms using Python. While it is important eventually to be able to design more efficient algorithms for many situations, we need to learn to walk before we learn to run. Even when we have more experience, brute force algorithms still have their uses. If you find yourself at a technical interview where a solution to a computational problem is required, it is often worth starting by producing a brute force solution and then going on to discuss why it needs improving and how you might do this.
In future lessons we will look some at the many possible alternatives to brute force search or exhaustive search for solving a variety of problems.
Until then, happy computing!
Featured image courtesy of Venkatesh Rao
