# The Invent with Python Blog

Writings from the author of Automate the Boring Stuff.

# Combinations and Permutations in Python with itertools

Sat 03 July 2021    Al Sweigart

(The following information and more can be found from my upcoming, to-be-announced book on recursive algorithms. I'll update this post when the book is released in 2022.)

If you a list, dictionary, or other iterable object of values you need to generate combinations and permutations from, Python has the built-in `itertools` module as part of its standard library. The permutations of an iterable are every possible ordering of all of the values, while the combinations are every possible selection of some, none, or all of the values. For example, the permutations and combinations of the set `{'A', 'B', 'C'}` are:

PermutationsCombinations
ABC, ACB, BAC, BCA, CAB(none), A, B, C, AB, AC, BC, ABC

You can also reuse the values multiple times, which is called permutations with repetition and combinations with repetition (also called replacement):

Permutations with RepetitionCombinations with Repetition
AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC(none), A, B, C, AA, AB, AC, BB, BC, CC, AAA, AAB, AAC, ABB, ABC, ACC, BBB, BBC, BCC, CCC

(Note that permutations with repetition is effectively the same as a password cracker that tries every possible combination of characters to brute force a password.)

The number of permutations and combinations quickly grows when more values are added to the iterable object. The total number of permutations and combinations is given in the following:

 Permutations of n Values Combinations of n Values Without Repetition n! 2^n With Repetition n^n "2n choose n", that is, (2n)! / (n!)^2

But to have Python generate permutations, you can use `itertools.permutations()`:

```>>> import itertools
>>> for v in itertools.permutations(['A', 'B', 'C']):
...   print(v)
...
('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')
>>>
>>> list(itertools.permutations(['A', 'B', 'C']))
[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

>>> list(itertools.permutations(['A', 'B', 'C'], 2))
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
>>> list(itertools.permutations(['A', 'B', 'C'], 1))
[('A',), ('B',), ('C',)]
```

To have Python generate combinations, you can use `itertools.combinations()`:

```>>> import itertools
>>> for v in itertools.combinations(['A', 'B', 'C'], 2):
...   print(v)
...
('A', 'B')
('A', 'C')
('B', 'C')

>>> list(itertools.combinations(['A', 'B', 'C'], 1))
[('A',), ('B',), ('C',)]
>>> list(itertools.combinations(['A', 'B', 'C'], 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]
>>> list(itertools.combinations(['A', 'B', 'C'], 3))
[('A', 'B', 'C')]
```

Note that the `combinations()` function takes a second argument for the number of values to select. To get all combinations (also called the power set), you'll need to make multiple calls to `combinations()`:

```>>> powerSet = []
>>> import itertools
>>> for k in range(4):
...   powerSet.extend(itertools.combinations(['A', 'B', 'C'], k))
...
>>> powerSet
[(), ('A',), ('B',), ('C',), ('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B', 'C')]
```

To get permutations with repetition/replacement, call `itertools.product()` and pass the size of the iterable object for its `repeat` argument:

```>>> import itertools
>>> for v in itertools.product(['A', 'B', 'C'], repeat=3):
...   print(v)
...
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'A', 'C')
('A', 'B', 'A')
('A', 'B', 'B')
('A', 'B', 'C')
('A', 'C', 'A')
('A', 'C', 'B')
('A', 'C', 'C')
('B', 'A', 'A')
('B', 'A', 'B')
('B', 'A', 'C')
('B', 'B', 'A')
('B', 'B', 'B')
('B', 'B', 'C')
('B', 'C', 'A')
('B', 'C', 'B')
('B', 'C', 'C')
('C', 'A', 'A')
('C', 'A', 'B')
('C', 'A', 'C')
('C', 'B', 'A')
('C', 'B', 'B')
('C', 'B', 'C')
('C', 'C', 'A')
('C', 'C', 'B')
('C', 'C', 'C')
>>> list(itertools.product(['A', 'B', 'C'], repeat=3))
[('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')]
```

To get combinations with repetition/replacement, call `itertools.combinations_with_replacement()`:

```>>> import itertools
>>> for v in itertools.combinations_with_replacement(['A', 'B', 'C'], 3):
...   print(v)
...
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'A', 'C')
('A', 'B', 'B')
('A', 'B', 'C')
('A', 'C', 'C')
('B', 'B', 'B')
('B', 'B', 'C')
('B', 'C', 'C')
('C', 'C', 'C')
>>> list(itertools.combinations_with_replacement(['A', 'B', 'C'], 3))
[('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'C'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'C'), ('C', 'C', 'C')]
```

If you're like me and you had trouble remembering the differences between permutations and combinations, with and without repetition, and which Python functions implement them, bookmark this page to have easy access in the future.