itertools module - permutations

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

• itertools module - general iterators
• itertools module - infinite iterators
• itertools module - combinatoric iterators
• itertools module - cartesian product
• itertools module - combinations