Permutations algorithm walkthrough (Part 2)

Congratulations, you made it to part 2 ! To access part 1, click here.

We’ll start by creating our initialize_counter function:

It’s pretty straightforward: our function takes in a value n (the length of the input list to our permutations function). Then, we return a list of length n with values of 0. For n = 3, the resulting list is: [0,0,0]. We do this by using list comprehensions.

Now, let’s create our increment counter function.

Here is what the completed function looks like:

Our function takes a list (our counter) as input.

On the first line, we set a variable n equal to the length of our counter (or number of elements).

Next, we use a for loop to iterate through our input list, starting with the last index (n-1).

for i in range(n-1, -1, -1): 
  arr[i] += 1 
  if arr[i] == n: 
    arr[i] = 0
  else: 
    break

At each iteration, we add 1 to the element located at index i of our input list; if the element located at index i is equal to n, we revert its value back to 0 and the loop goes on.

Otherwise, we break from the loop early.

For the following explanation, we’ll assume a value of n = 3:

input list: [0,0,0]

Inside our for loop, we start by incrementing the value at index 2 (i = n-1) of our input list; the list becomes: [0,0,1]

We then verify if our value at index 2 is equal to n (for our example, n=3), since 1 is not equal to 3, the else statement executes and we break from the loop early.

Let’s see what happens when an element of our counter reaches a value of n:

Let’s assume the following input list: [0,0,2]

At that stage, our counter has already been through n states:

Its initial state: [0,0,0]
First increment: [0,0,1] 
Second increment:[0,0,2]

Now, when we pass the counter to our increment function, and that we increment its last element, our conditional of arr[i] == n evaluates to true, and the last element reverts to 0:

if arr[i] == n: 
  arr[i] = 0

But this time, instead of breaking from the loop early, our value of i gets decremented by 1, and upon re-entering the loop, the element at index 1 of our counter gets incremented and we end up with the following list: [0,1,0]

Now, here is the completed program with all of its components:

You may want to go through part 1 again, click here to return to part 1.