Click here to Skip to main content
15,394,023 members
Articles / Programming Languages / Python
Tip/Trick
Posted 28 Jan 2019

Tagged as

Stats

27.4K views
8 bookmarked

Recursive Permutations in Python

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
28 Jan 2019CPOL3 min read
Computing permutations using recursion, in Python, for the absolute beginner

Permutations example image

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']

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

  • 27th January, 2019 - First revision

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

CPallini
Software Developer (Senior) Biotecnica Instruments S.p.A.
Italy 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 [^].





Comments and Discussions

 
-- There are no messages in this forum --