Combinations and Permutations in Python with itertools
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 are:
| Permutations | Combinations |
|---|---|
| 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 Repetition | Combinations 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.
Learn to program for free with my books for beginners:
Sign up for my «Automate the Boring Stuff with Python» online course with this discount link.
Комбинаторика в Python
Стандартная библиотека python, начиная с версии 2.2, предоставляет множество средств для генерирования комбинаторных объектов, но в интернете мне не удалось найти ни одной статьи, которая подробно рассказывала бы о работе с ними. Поэтому я решил исправить это упущение.
Начну с того, что расскажу о комбинаторике и ее основных формулах. Если же вы уже знакомы с этим разделом математики — можете пропустить эти абзацы.
Допустим, у нас есть строка, состоящая из n разных букв и мы хотим вычислить все способы переставить эти буквы местами так, чтобы получить новую строку. На первую позицию в строке мы можем выбрать одну из n букв, имеющихся у нас, на вторую позицию одну из n-1-ой буквы и так далее. В итоге получаем произведение n (n-1)… *1 = n! количество перестановок из n элементов без повторений.
Теперь представим, что количество букв в строке ограничено. У нас есть n доступных букв и мы хотим вычислить количество способов составить из них строку длины k, где k < n, каждую букву мы можем использовать лишь единожды. Тогда на первую позицию в строке мы можем поставить одну из n букв, на вторую позицию одну из n-1 буквы и на k-ую позицию одну из n-k+1 буквы. Общее количество строк будет равно n (n — 1) (n — 2) … (n — k + 2) (n — k + 1) = n!/(n-k)! количество размещений из n по k. Если же уникальность букв не требуется, то мы получим формулу n. nn = n^k количество размещений из n по k с повторениями.
Рассмотрим случай посложнее, у нас есть n коробок каждая из которых содержит множество конфет одного вкуса, но в разных коробках вкусы разные. Сколько существует способов составить подарок другу из k конфет, при чем один и тот же вкус может встречаться любое количество раз? Так как порядок для нас значения не имеет, давайте разложим подарочные сладости следующим образом: в начале будут лежать последовательно конфеты первого вкуса, затем второго и так далее, а между конфетами разных вкусов положим спички, если конфеты какого-то вкуса отсутствуют в нашем подарке — спички, которые должны были окаймлять этот вкус слева и справа будут стоять рядом. Того у нас получится последовательность, состоящая из k конфет и n-1 спички, ибо вкусов всего n, а спички разделяют их. Теперь заметим, что по расположению спичек, мы можем восстановить исходное множество. Тогда ответом будет количество способов разместить n-1 спичку в n+k-1 ячейку без учета порядка, что равно количеству сочетаний из n+k-1 по n-1, формула: количество сочетаний из n по k с повторениями.
Теперь рассмотрим несколько задач на комбинаторику, чтобы закрепить материал.
Задача 1
Есть 20 человек, сколько существует способов разбить их на пары
Решение: возьмем первого человека, сколько существует способов выбрать ему пару: , возьмем второго человека, сколько существует способов выбрать ему пару: . Ответ: 19. = 654729075
Задача 2
Есть 10 мужчин и 10 девушек, сколько существует способов разбить их на компании, состоящие из одинакового количества и мужчин и девушек, пустая компания не считается
Решение:
Cпособ 1: количество способов собрать компанию из одного мужчины и одной девушки равно произведению количества способов выбрать одну девушку и количества способов выбрать одного мужчину. Количество способов выбрать одну девушку из 10 равно сочетанию из 10 по 1 без повторений, с мужчинами аналогично, поэтому возведем в квадрат. Далее аналогично вычислим сочетания из 10 по 2, из 10 по 3 и так далее до сочетания из 10 по 10. Итоговая формула: .
Способ 2: рассмотрим множество мужчин, входящих в компанию и множество девушек, не входящих в нее. По этому множеству можно однозначно восстановить компанию, а количество людей в нем всегда равно 10, так как , k — количество мужчин в компании, — количество девушек, не вошедших в нее. Количество таких множеств равно количеству сочетаний из 20 по 10, в конечном ответе мы также вычтем единицу, чтобы не учитывать пустую компанию, когда в нашем множестве 10 девушек. Итоговая формула: .
Итак, мы разобрались с теорией, теперь научимся генерировать комбинаторные объекты с помощью стандартной библиотеки python.
Работать мы будем с библиотекой itertools
С помощью функции permutations можно сгенерировать все перестановки для итерируемого объекта.
Пример 1
for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba Исходя из второго вызова заметим, что одинаковые элементы, стоящие на разных позициях, считаются разными.
Пример 2
for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb Размещение отличается от перестановки ограничением на количество доступных ячеек
Пример 3
for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb ccC помощью размещений с повторениями можно легко перебрать все строки фиксированной длины, состоящие из заданных символов
Пример 4
for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd С помощью сочетаний без повторений можно перебрать все наборы не повторяющихся букв из заданной строки, массива или другого итерируемого объекта без учета порядка
Пример 5
for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd Результат аналогичен вызову combinations, но в результат также добавлены множества с одинаковыми элементами.
Материалы:
Н.В. Горбачев «Сборник олимпиадных задач по математике»
Документация по python на русском