Back to index

How to find permutations of n numbers with Python the hard way

Suppose we want to find permutations of numbers from 1 to n using Python. Easily done, right ? Just use the standard library function `itertools.permutations` to find the n! number of permutations. But in this post, I am going to illustrate how you can list them, starting from scratch. I will show a few approaches, both recursive and non-recursive.

First let us consider how we find permutations with paper and pencil. With the numbers {1, 2, 3}, for example, we proceed as follows:

1 ---> 2 ---> 3
1 ---> 3 ---> 2

2 ---> 1 ---> 3
2 ---> 3 ---> 1

3 ---> 1 ---> 2
3 ---> 2 ---> 1

That is, for each position in turn, we consider each of the remaining numbers, starting with the full set of inputs. This method is not exactly simple to code. A recursive function for it is shown below:

``````def perm(n):
"""Generates a list of n! permutations of the numbers from 1 to n."""

nums = list(range(1, n+1))
result = []

def permut(nums, curr):

if nums == []:
result.append(list(curr))    # (1)
return

for i in range(len(nums)):
x = nums.pop(i)
curr.append(x)
permut(nums, curr)
nums.insert(i, x)
curr.pop()

permut(nums, [])
return result
``````

The function `perm` follows the algorithm outlined above. It contains an inner recursive function `permut` that generates the individual permutations that get appended to the `result` list. At line (1), a copy of the current permutation `curr` is made to prevent an aliasing effect in the `result` list. In the `for` loop, numbers are succesively popped from the main list and appended to the permutation that is getting built up. The recursive call eventually (in the base case) builds and appends the permutation to the result list. Following this call, we reset both the `nums` and the `curr` lists to prepare for the next permutation.

A method that is more straight-forward to code is as follows.

Start with a list containing 1. Insert 2 on either side to create 2 more lists - [1, 2] and [2, 1]. Then insert 3 in each of the 3 positions of these 2 lists to create the final set of 6 lists or permutations - [3, 1, 2], [1, 3, 2], [1, 2, 3] and [3, 2, 1], [2, 3, 1], [2, 1, 3].

This can be programmed easily using recursion:

``````def perm(n):
"""Returns a list of all the permutations of the first n positive integers -
each permutation being a list itself. That is, the result is a list of
lists."""

if n == 1:
return [[1]]

result = []

for item in perm(n-1):
for i in range(len(item)+1):
x = list(item)
x.insert(i, n)
result.append(x)

return result
``````

Given below is a non-recursive solution to the problem using an explicit stack (the method is the same - insert a number into each position of a list):

``````def permstack(n):
"""Uses a list as a stack. Yields each permutation as a list."""

stack = []

stack.append([1])    # doing a push

while stack:
item = stack.pop()
i = len(item) + 1
if i > n:
yield item
continue
for j in range(i):
x = list(item)
x.insert(j, i)
stack.append(x)    # push
``````

An example. When running `permstack(3)`, the stack, at some stage, will contain [[2, 1], [3, 1, 2], [1, 3, 2]] with one permutation [1, 2, 3] yielded.

There is really no reason why you would use a procedure such as any of the above to find permutations when you have a standard library function `itertools.permutations`. It serves an educational purpose - you know the process by which permutations can be listed out, instead of having the black box of a built-in function.

One last thing - the above functions can be easily modified to return permutations of n integers, starting from 0. Thus you have all the arrangements of indexes of a sequence. From this you can get the permutations of arbitrary, possibly non-unique, elements (like strings, floats, etc.) of the sequence.

Back to index