Permutations algorithm walkthrough (Part 1)

(this is a 2-part series)

note: This algorithm can be implemented using the built-in Python generators.

In this short-series, I will walk you through the implementation of an iterative algorithm for generating permutations for a given input using Python. Our program will produce all permutations, with repeating elements.

We’re going to break down our program into several components:

1. A counter, which will keep track of permutations
2. An increment function for the counter
3. The main function to our algorithm which will bring all of the components together (part 1 of our 3-part series)

We will be using a counter to keep track of permutations:

For an input list of size 3, our counter will function this way:

000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, …

We increment by 1 at every step, the result being the state for the next permutation.

You can see that the last digit reverts to 0 after reaching 2: that’s because we use 0, 1, and 2 to represent the first, second and third indices of our input list. (for a list of size 3)

In other words, each digit maps to elements of our input list.

For an input list [‘a’, ‘b’, ‘c’], the state 000 represents the permutation aaa, 001: aab, 002: aac, 010: aba, …

We’ll start by writing the main function of our program. We’ll write it as if the other functions were already written (although we’ll deal with them later).

Here’s what the function will look like once it’s done:

Now, let’s work through it line by line:

def permutations(arr): 
  out = [] #   we initialize our output list
  n = len(arr)**len(arr) # n: total number of permutations

Our permutations function takes a list as its input. Then, on the first line of our function we initialize a variable ‘out’ which will hold our output, ie. our permutations.

On the following line, we initialize a variable n to the total number of permutations for a list of size N.

For an input list of size 3, we get 3 x 3 x 3 (nⁿ) permutations, or a total of 27. (assuming repeating elements)

def permutations(arr): 
  out = [] 
  n = len(arr)**len(arr)
counter = initialize_counter(len(arr)) # we initialize our counter

Then, we initialize a variable ‘counter’ using the initialize_counter function (we’ll implement it later), which will return a list with each element initialized to 0. example: [0, 0, 0] (for an input list of size 3)

for i in range(n): # we go through n iterations
  new_permutation = [] # initialize list to hold next permutation
  for elem in counter: # we loop through each element of our counter
    new_permutation.append(arr[elem]) # append new permutation

Next, we use a for loop to go through n iterations (remember, n represents the total number of permutations) to generate all permutations.

The first line inside the for loop sets up an empty list for each permutation. Then, we need an inner for loop to go through each integer x of our counter list and generate a new permutation by getting each value stored at index x in our input list.

for i in range(n): 
  new_permutation = [] 
  for elem in counter: 
    new_permutation.append(arr[elem])
  out.append(new_permutation)
  increment_counter(counter)
return out

Once we’re done with generating our new permutation, we append it to our output list, and we increment our counter by passing it to the increment_counter function.

Finally, we return our output list and we’re done with our main function.

Here is the completed function again:

Continued in Part 2…