15,607,524 members
Articles / Programming Languages / Python
Tip/Trick
Posted 28 Jan 2019

31K views
8 bookmarked

# Recursive Permutations in Python

Rate me:
Computing permutations using recursion, in Python, for the absolute beginner

## Introduction

Some people find it hard to understand recursive algorithms.

This tip shows the absolute beginner how to find permutations using recursion in `Python`.

## Background

The idea for this tip comes from a Q&A question: the poor OP 'rolled the head' for three days trying to figure out how a small snippet of `Python` code was able to produce all the permutations of the items of an input list. In the hope of stopping such dangerous movements, I am trying to shed some light on the argument.

## 1. The Problem

The problem is: find all the permutations of a set. Roughly speaking, we must find all the different arrangements of the elements of the set.

## 2. The 'Paper & Pencil' Approach

Let's start simple. Consider a set having the single element `1`. Clearly, the only arrangement of this poor, lonely item is itself.

### 2.1 Permutations of {1}

`P[1]  =  1`

Now consider two elements, all the permutations reduce to a simple swap.

### 2.2 Permutations of {1,2}

```           1 2
P[1 2]  =
2 1```

Finally, consider three elements: with a little effort, we write:

### 2.3 Permutations of {1,2,3}

```             1 2 3

1 3 2

2 1 3
P[1 2 3]  =
2 3 1

3 1 2

3 2 1```

## 3. The Emerging Pattern

Considering the last example, there is an emerging pattern: first, we have chosen the first element of the `{1,2,3}` set ( namely `1`).

Then, with the remaining items (i.e., `2` and `3`), we have proceeded following the recipe `2.2`, that is, we have swapped them.

Finally, we have chosen, respectively, the second and third item and made similar operations on the remaining ones.

To summarize:

```                          1 2 P[3]  =  1 2 3
1 P[2 3]  =
1 3 P[1]  =  1 3 2

2 1 P[3]  =  2 1 3
P[ 1 2 3] =  2 P[1 3]  =
2 3 P[1]  =  2 3 1

3 1 P[2]  =  3 1 2
3 P[1 2]  =
3 2 P[1]  =  3 2 1 ```

Now, we can easily generalize:

```                1 P[2 3 .. N]
2 P[1 3 .. N]
P[1 2 .. N] =   ..
..
N P[1 2 .. (N-1)]
```

That is:

The permutations of `N` elements are found joining iteratively each of them with the permutations of the remaining ones.

Wow, we've just found an algorithm defined by means of itself. Sound familiar? It is a recursive algorithm.

## 4. Recursive Algorithm Implementation in Python

Python
```def permute(s):
out = []
if len(s) == 1:
return s
else:
for i,let in enumerate(s):
for perm in permute(s[:i] + s[i+1:]):
out += [let + perm]
return out```

Called this way:

Python
```l = permute(['1','2','3','4'])
print(l)```

It produces the output:

```['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431',
'3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132', '4213', '4231', '4312', '4321']```

Such code is not mine, it is the original snippet the OP was asking for explanations (as a matter of fact, I am more inclined towards `Lua` than `Python` and I had to lookup the enumerate [^] function in `Python`'s documentation in order to fully understand the code).

## 5. Trying to Understand the Code by 'Mental Execution'

The program is a straightforward (possibly inefficient, see the remarks at the bottom of the page) implementation of the recursive algorithm. Now we try to 'mental execute' it in order to shed some light for the absolute beginner.

### 5.1 Mental Execution of permute(['1']).

This is trivial, since `len(['1]')` is `1` then the first branch of the `if` condition is taken and the return value is `['1']` itself (this complies with rule `2.1`).

### 5.2 Mental Execution of permute(['1','2']).

Now `len(['1','2'])` is `2`, hence the `else` branch of the `if` is taken. The:

Python
```for i,let in enumerate(s):
```

statement is going to produce `2` iterations. Focusing ourselves on the first one, we have (thanks to `enumerate`) `i = 0, let = '1'`. With such values, the:

Python
```for perm in permute(s[:i] + s[i+1:]):
```

that is:

Python
```for perm in permute(['2']):
```

(because `s[:0] = []`,   `s[1:] = ['2']`) is reached.

In such a statement, we eventually see recursion in action: `permute` calling itself.

We already know (from `5.1`) that `permute['2']` returns `'2'`, hence the `for` is going to perform a single iteration. Inside such an iteration, we hit:

Python
```out += [let + perm]
```

That is:

Python
```out += ['1'+'2']
```

or:

Python
```out = ['12']
```

With the same reasoning, we expect the (outer loop) second iteration contribution to be:

Python
```out += ['2'+'1']
```

giving the final result:

Python
```out = ['12', '21']
```

### 5.3 Mental Execution of permute(['1','2','3']).

Armed with experience, we quickly consider this case.

At first iteration:

```i=0
let='1'
permute(s[:0] + s[1:]) = permute([] + ['2','3']) = ['23','32']```

That is:

Python
```for perm in ['23', '32']:
out += ['1' + perm]
```

Which gives:

Python
`out = ['123', '132']`

Second (outer loop) iteration goes on:

```i = 1
let = '2'
permute(['1'] + ['3']) = ['13','31']```

contributing with:

Python
`out += ['213', '231']`

In a similar way, third iteration contribution is:

Python
`out += ['312', '321']`

So that the final result is:

Python
`out = ['123', '132', '213', '231', '312', '321']`

## Remarks

The `permute` function, while showing a straightforward implementation of a recursive algorithm is not a champion of performance. A comparison with an equivalent application, implemented by means of the (`itertools` package's) permutations [^] function shows the latter is about `7x` faster on producing the permutations list of `10` items (without console output, in both cases).

## History

• 27th January, 2019 - First revision

Written By
Software Developer (Senior) Biotecnica Instruments S.p.A.
Italy

Debugging? Klingons do not debug. Our software does not coddle the weak. Bugs are good for building character in the user.
-- The Klingon programmer

Beelzebub for his friends [^].