This example uses an algorithm to find a number's prime factors. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Recursively generate permutations of values in Python

[Permutations of the letters A, B, and C]

The permutations of a set of values consists of all possible orderings of those values. For example, here are the six possible permutations of the values ['A', 'B', 'C']:

['A', 'B', 'C'] ['A', 'C', 'B'] ['B', 'A', 'C'] ['B', 'C', 'A'] ['C', 'A', 'B'] ['C', 'B', 'A']

This example shows how to find a set's permutations in two ways: using itertools and from scratch.

Using itertools

The itertools library provides methods for performing various iteration-related tasks. For example, repeat lets you repeat an element a given number of times and cycle lets you repeatedly cycle through a set of values.

The permutations method returns an iterator that generates tuples that hold a set's permutations.

The program uses the following code to use the itertools library to display permutations.

values = ['A', 'B', 'C'] # Use itertools. import itertools for permutation in itertools.permutations(values): print(permutation) print('***************')

This code defines the values list and then imports itertools. It uses the itertools permutations method to get the permutations and loops through them to display them.

Note that the permutations method returns an iterator not a list. Use the list function to turn it into one if you want.

From Scratch

The itertools library's permutations method is easy to use, but sometimes it's nice to be able to generate your own permutations. That way you can take special actions like skipping some permutations if they don't meet your needs. (I'll post an example later that uses branch and bound and that avoids examining some permutations. For now, just take it on faith that it's sometimes useful to roll your own.)

The following get_permutations method builds a list holding all of a set's permutations.

def get_permutations(values, permutations, is_used, current_permutation): ''' Find the permutations of the values. Add any permutations found to the permutations list. ''' # See if we have a full permutation. if len(current_permutation) == len(values): # All items are in the current permutation so it's full. permutations.append(current_permutation.copy()) else: # The current permutation isn't full. # Search for an unused value. for i in range(len(values)): if not is_used[i]: # This value isn't currently in use. # Add it to the current permutation. current_permutation.append(values[i]) is_used[i] = True get_permutations(values, permutations, is_used, current_permutation) # Remove the value from the current permutation. current_permutation.pop() is_used[i] = False

This method's parameters are:

values - The set of values that we want to permute
permutations - An input/output list into which we will put the permutations as we generate them
is_used - A list indicating which values are in the current permutation, for example, is_used[i] is True if value i is in the current permutation
current_permutation - A list holding the values in the current permutation that we are building

Here's how the method works.

First, if current_permutation contains all of the values, then it is a complete permutation so the method adds it to the permutations list.
Otherwise, we need to add more values to the current permutation to make it complete. To do that, the code makes variable i loop through the values' indices. If is_used[i] is False, then the code does the following:
1. Add values[i] to the current solution.
2. Set is_used[i] = True to indicate that the value is in use.
3. Call get_permutations recursively to fill in the rest of the current permutation.

The recursive call makes other recursive calls until the program reaches a point where there's a complete permutation and the program adds it to the permutations list. After the recursive call returns, it has added all of the permutations that start with the incoming current_permutation followed by value[i].

Now the method needs to consider permutations that start with incoming current_permutation followed by other values. To do that, it continues as follows:

Use pop to remove values[i] from the end of current_permutation.
Sets is_used[i] to False to indicate that values[i] is no longer in current_permutation.
Continues the for loop to consider other values.

The following code shows how the program calls get_permutations.

# Find the permutations ourselves. is_used = [False for _ in values] permutations = [] current_permutation = [] get_permutations(values, permutations, is_used, current_permutation) for permutation in permutations: print(permutation)

This code create is_used, permutations, and current_permutations lists and passes them into the get_permutations method. It then prints the permutations as before.

Download the example to see additional details.