In this blog post I will describe how we can create permutations in Python 3.4.

Problem
Suppose you are given the list [0, 1, 2] and you wanted to create all six permutations of this list, i.e. [2, 1, 0], [1, 2, 0], [1, 0, 2], [2, 0, 1], [0, 2, 1] and [0, 1, 2]. Here are two methods that you can use.

Method 1: Inserting at all positions
In this method we will go through the numbers from 0, 1, …, n-1. Each time we process a new number we insert it at all possible positions. For example,
– we start with 0.
– The next number is 1 which we can insert before and after the 0, so we get 10 and 01.
– The next number to add is 2. For 10 we can add 2 (i) before 1, (ii) between 1 and 0 and (iii) after 0. To make it clearer, we can write 10 as _1_0_ where the underscores are the possible positions for the 2. Doing so yields the permutations (i) 210, (ii) 120 and (iii) 102.

The following image illustrates this:

Let’s focus on the step where we insert a new number at all possible positions. As an example we start with the [0, 1] and insert 2. Here is the code in Python:

p = [1, 0]
i = 2

# there are three possible positions: _1_0_
# insert 2 at positions 0, 1, 2
for pos in range(len(p)+1):
    print( p[:pos] + [i] + p[pos:] )

The output is:

[2, 1, 0]
[1, 2, 0]
[1, 0, 2]

After we have understood how this step works we can now implement a function that creates all permutations of the numbers 0, 1, …, n-1. Here is the code in Python 3.4:

def create_perm(n):
    L = [[0]]
    for i in range(1, n):
        L_new = []
        for p in L:
            for pos in range(len(p)+1):      # important: include len(p)
                p_new = p[:pos] + [i] + p[pos:]
                L_new.append(p_new)
        L = L_new
    return L


my_permutations = create_perm(3)
for p in my_permutations:
    print(p)
print("number of permutations:", len(my_permutations))

The output is:

[2, 1, 0]
[1, 2, 0]
[1, 0, 2]
[2, 0, 1]
[0, 2, 1]
[0, 1, 2]
number of permutations: 6

Note: This method is not efficient for two reasons. First, we are creating new lists at each step which is expensive. Second, in the end we return a list that possibly is very large and therefore occupies a lot of memory.

Method 2: Use itertools.permutations()
A better method is to use the built-in generator itertools.permutations(). One reason why this method is more efficient than the first is that itertools.permutations() is a generator, and as such it does not allocate additional memory for a list.

Here is the code in Python:

import itertools

my_permutations = itertools.permutations(range(3))

cnt = 0
for p in my_permutations:
    print(p)
    cnt += 1

print("number of permutations:", cnt)

The output is:

(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
number of permutations: 6

Exercise
Given the list L = ["Alice", "Bob", "Eve"] print all permutations of L.

Solution
We can simply pass the list to itertools.permutations(), see the comment in the code here:

import itertools

L = ["Alice", "Bob", "Eve"]

for perm in itertools.permutations(L):
    print(perm)

The output is:

('Alice', 'Bob', 'Eve')
('Alice', 'Eve', 'Bob')
('Bob', 'Alice', 'Eve')
('Bob', 'Eve', 'Alice')
('Eve', 'Alice', 'Bob')
('Eve', 'Bob', 'Alice')