# itertools module - permutations

Categories: python standard library

The `itertools.permutations`

function accepts a single iterable and creates every possible permutation of input values.

## What are permutations

If we have a set of distinct values, for example the set of letters A, B, C, and D, there are different ways we can arrange those items. For example ABCD, CADB, or DCBA. Each unique arrangement is called a *permutation* of the values. Each permutation contains the same 4 values, but in a different order, with no repeated values permitted.

In this case, the total number of permutations can be calculated as follows:

- There are 4 possible values for the first letter, it can be A, B, C, or D.
- Having chosen the first letter, there are 3 possible values (since one letter has been used and repeated values are not allowed).
- After choosing the first two letters, there are only two remaining choices for the third letter.
- There is then only one possible choice for the fourth letter.

This means that the total number of permutations of 4 items is 4 x 3 x 2 x 1, or 4 factorial. That gives 24 items. In general, the number of permutations of *n* objects is *n* factorial.

See this article on graphicmaths.com for more information on the mathematics of permutations.

## The itertools permutations function

If we have a list of possible values, we can create all the permutations using the `permutations`

function of the `itertools`

module, like this:

```
import itertools
k = ["A", "B", "C", "D"]
perms = itertools.permutations(k)
for t in perms:
print(t)
```

In this case, we create the possible values as a list. The `permutations`

function can accept any iterable, which could be a tuple, string, or a lazy iterable.

The function returns an iterator, holding all the possible permutations. Remember that we can't just print an iterator, because that would only show the iterator object rather than the values it contains (see the discussion here). Instead, we loop over the values, printing them out. Here is what we get:

```
('A', 'B', 'C', 'D') ('A', 'B', 'D', 'C') ('A', 'C', 'B', 'D') ('A', 'C', 'D', 'B')
('A', 'D', 'B', 'C') ('A', 'D', 'C', 'B') ('B', 'A', 'C', 'D') ('B', 'A', 'D', 'C')
('B', 'C', 'A', 'D') ('B', 'C', 'D', 'A') ('B', 'D', 'A', 'C') ('B', 'D', 'C', 'A')
('C', 'A', 'B', 'D') ('C', 'A', 'D', 'B') ('C', 'B', 'A', 'D') ('C', 'B', 'D', 'A')
('C', 'D', 'A', 'B') ('C', 'D', 'B', 'A') ('D', 'A', 'B', 'C') ('D', 'A', 'C', 'B')
('D', 'B', 'A', 'C') ('D', 'B', 'C', 'A') ('D', 'C', 'A', 'B') ('D', 'C', 'B', 'A')
```

There are 24 items here, as we would expect (4 factorial).

## Lexicographic order

The output values of the `permutations`

function are produced in a specific order:

- The first element is taken from the input in the order the input elements occur - in this case, A, then B, then C, then D.
- For each first element, the second element is taken from the remaining elements, again in the order they occur.
- And so on.
- This is called lexicographic order (see this article on graphicmaths.com.

If the input values are sorted, then the output values will be in sorted order (as they are in this case).

However, the algorithm takes no account of the values of the input elements. If the input values are not sorted, the output values will not be sorted either.

## Perm r from n

Given a set of values A, B, C, and D, we might want to know all the possible orderings of any 2 values from that set. This is called "perm 2 from 4". In general, we call this "perm r from n".

The `permutations`

function has an optional parameter `r`

that allows us to do this:

```
k = ["A", "B", "C", "D"]
perms = itertools.permutations(k, r=2)
for t in perms:
print(t)
```

This creates the following set of values:

```
('A', 'B') ('A', 'C') ('A', 'D') ('B', 'A')
('B', 'C') ('B', 'D') ('C', 'A') ('C', 'B')
('C', 'D') ('D', 'A') ('D', 'B') ('D', 'C')
```

You will notice that there are fewer values than a simple permutation. In fact, there are half as many. The reason for this is explained in the graphics maths article, but essentially the number of permutations is *n* factorial divided by *r* factorial, which in this case is 24/2 = 12.

## Permutations with replacement

So far we have looked at permutations where each value from the input set can only be used once. There is another form of permutation, *permutations with replacement* that allows items to be used more than once.

As an example, consider a PIN that you might use with a bank card. This is often a 4 digit number. You need to know the right digits, in the right order, so it appears to be a permutation. It could be 1234, or it could be 5567, or even 8888. A digit can be reused.

To see where the name come from, imagine we had 10 cards with the digits 0 to 9. If we draw 4 cards at random, we will get a random 4-digit PIN, but of course all the digits would be different because each card can only be drawn once.

What if we did it a little differently? We draw a card, note its value, and then place it back in the deck (ie replace it). That way it is possible to draw the same card twice or more.

The `itertools`

library doesn't provide a `permutations_with_replacement`

function. That is because permutation with replacement is identical to a Cartesian product. See that article for more details. We can create a 4 digit PIN like this:

```
k = range(10)
perms = itertools.product(k, repeat=4)
```

There are 10,000 possibilities so we won't list them.

## Permutations vs combinations

Permutations are closely related to combinations. The difference is that order matters for permutations, but not for combinations.

For example, the two PINs 1234 and 4321 have the same elements but in a different order. They are different permutations but the same combination. Since a PIN is a permutation, those two are not considered to be the same PIN.

The numbers in a lottery draw are different. The set of balls (1, 5, 11, 23, 37, 42), or the set (11, 42, 5, 37, 23, 11), are the same balls drawn in a different order. They are the same combination but different permutations. All that matters in the lottery is the combination of balls, the order is irrelevant, so if those are your numbers you have won either way.

## Repeated input values

One this to bear in mind is that the `permutations`

function treats all the input values as being unique. So for example if we started with this list:

```
k = ["A", "B", "B", "D"]
```

The list would be treated as a list of 4 different strings, where two of the strings just happen to have the same value, "B". The Python documentation states that *elements are treated as unique based on their position, not on their value*.

We would still get 24 permutations. Of course, some of those outputs would be the same. For example, the sequence BABD would appear twice with the two Bs in a different order.

The reason the `permutations`

function works this way is most likely for efficiency. Eliminating duplicates takes time, and that would slow the function down. Ideally `itertools`

might have provided a separate function to create unique permutations, but unfortunately, it doesn't have such a function.

If you have duplicate inputs and require unique outputs, there are a couple of options:

- Use the
`more_itertools`

library. This includes many extra functions that work in a similar way to`itertools`

. It isn't a standard Python library so you will need to install it, - If you don't wish to add the extra dependency of the
`more_itertools`

library, you will need to check the output from the`permutations`

function and remove any duplicates.

## See also

## Join the PythonInformer Newsletter

Sign up using this form to receive an email when new content is added:

## Popular tags

2d arrays abstract data type alignment and angle animation arc array arrays bar chart bar style behavioural pattern bezier curve built-in function callable object chain circle classes clipping close closure cmyk colour combinations comparison operator comprehension context context manager conversion count creational pattern data science data types decorator design pattern device space dictionary drawing duck typing efficiency ellipse else encryption enumerate fill filter font font style for loop formula function function composition function plot functools game development generativepy tutorial generator geometry gif global variable gradient greyscale higher order function hsl html image image processing imagesurface immutable object in operator index inner function input installing iter iterable iterator itertools join l system lambda function latex len lerp line line plot line style linear gradient linspace list list comprehension logical operator lru_cache magic method mandelbrot mandelbrot set map marker style matplotlib monad mutability named parameter numeric python numpy object open operator optimisation optional parameter or pandas partial application path pattern permutations pie chart pil pillow polygon pong positional parameter print product programming paradigms programming techniques pure function python standard library radial gradient range recipes rectangle recursion reduce regular polygon repeat rgb rotation roundrect scaling scatter plot scipy sector segment sequence setup shape singleton slice slicing sound spirograph sprite square str stream string stroke structural pattern subpath symmetric encryption template tex text text metrics tinkerbell fractal transform translation transparency triangle truthy value tuple turtle unpacking user space vectorisation webserver website while loop zip zip_longest