Recursive Permutations in Python

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

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:

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:

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:

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

that is:

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:

out += [let + perm]

That is:

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

or:

out = ['12']

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

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

giving the final result:

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:

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

Which gives:

out = ['123', '132']

Second (outer loop) iteration goes on:

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

contributing with:

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

In a similar way, third iteration contribution is:

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

So that the final result is:

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

And the task is complete.

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

• 27^th January, 2019 - First revision