Implementing permutations

Permutations as Coding Question

Preparing some coding questions for next interview for our team I was thinking of a good example to test candidates capabilities to understand how familiar are they with a concept of recursion.

A classic interview example is a an implementation of a power function:

#Function returning n! = 1*2*..*n
def power(n);

or another simple interview favourite:

#Function returning f(n) = f(n-1) + f(n-2)
def fibonacci(n);

To make things a bit more interesting I decided that to find a new and small programming problem which can be implemented using recursion.

I thought permutations are a good example. Specifically a function with following signature:

#Function returning permutations of input list a
def permute(a);

Outline of the Solution

The proposed approach is to use a recursion to implement the function generating all permutations for a given list.

For the purpose of this post let’s focus on a simple list of integers: [1,2,3] (since the implementation in next section is in Python I will stick to Python nomenclature).

On the first level of recursion the algorithm walks through the list and recursively call

def permute(a);

for sublists of the initial list. The consecutive sublists are generated from original list by removing 1st, 2nd up to last element of the original list i.e. for list [1,2,3] the 1st level sublists would be:

[1,2,3]:
        -> [2, 3] (removing ‘1’)

        -> [1,3] (removing ‘2’)

        -> [1,2] (removing ‘3’)

following on 2nd  level we have for 1st level sublists:

[2, 3]: 
       -> [3]

       -> [2]

[1,3]:
      -> [3]

      -> [1]

[1,2]:
      -> [2]

      -> [1] 

starting from [1, 2, 3], the next call to permute() will be with list [2, 3], following by call with arguments [2].

After final level of recursion has been reached the algorithm, will construct the permuted lists by adding the remove sublist element to the front of the sublist returned by next level of permutation for all sublists generated by next level e.g.

[1,2,3]:
        -> [2, 3]: 
                 -> [3] -> [2, 3] -> [1,2,3]
                 -> [2] -> [3, 2] -> [1,3,2]
and so on.

in result the list of generated permutations is as follows (1 * 2 * 3 = 6 permutations):

[1,2,3] 
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1] 

Implementation

Here is an example Python implementation of this algorithm:

#Function returning n! = 1*2*..*n
def permutate(a):
	partial = []
	if len(a) > 1:
		for index in range(0, len(a)):
			prefix = [a[index]]
			print "%s | %s\n" % (a[:index], a[index + 1:])
			sublist = permutate(a[:index] + a[index + 1:])
			for item in sublist:
				partial.append(prefix + item)
	else:
		partial = [a]
	return partial