Комбинаторика в 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 на русском
Перестановки и комбинации в Python
Перестановки и комбинации набора элементов в Python – это различные расположения элементов набора:
- Комбинация – это набор элементов, порядок которых не имеет значения.
- Перестановка – это расположение набора, в котором порядок имеет значение.
Перестановки вышеуказанного набора следующие:
('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A') Комбинации вышеуказанного набора, когда два элемента взяты вместе, следующие:
В этом руководстве мы узнаем, как получить перестановки и комбинации группы элементов в Python. Мы рассмотрим наборы символов и цифр.
Мы будем использовать методы combinations() и permutations() в модуле itertools.
Перестановки числовых данных
Чтобы использовать метод permutations() в модуле itertools, нам сначала нужно импортировать модуль.
Теперь давайте определим набор чисел.
Теперь, чтобы получить список перестановок, воспользуемся методом permutations().
perm_set = itertools.permutations(val)
Строка кода выше дает объект itertools. Чтобы напечатать различные перестановки, мы будем перебирать этот объект.
Мы получаем результат как:
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
Полный код этого раздела приведен ниже:
import itertools val = [1, 2, 3, 4] perm_set = itertools.permutations(val) for i in perm_set: print(i)
Перестановки строки
Далее мы узнаем, как получить перестановки символов в строке.
Мы будем использовать метод permutations(), но на этот раз мы передадим строку в качестве аргумента.
import itertools s = "ABC" perm_set = itertools.permutations(s) for val in perm_set: print(val)
('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A') Перестановки фиксированной длины
Мы можем найти перестановки набора, в котором мы берем только указанное количество элементов в каждой перестановке. Это похоже на nPr в области математики.
Код для поиска перестановок фиксированной длины приведен ниже:
import itertools val = [1, 2, 3, 4] perm_set = itertools.permutations(val,2) for i in perm_set: print(i)
(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)
Комбинации числовых данных
Так же, как метод permutations(), мы можем использовать combinations() также в itertools для получения комбинаций набора.
При вызове combinations() нам нужно передать два аргумента: набор для поиска комбинаций и число, обозначающее длину каждой комбинации.
import itertools val = [1, 2, 3, 4] com_set = itertools.combinations(val, 2) for i in com_set: print(i)
Комбинации строки
Мы также можем получить комбинации строки. Используйте следующий фрагмент кода:
import itertools s = "ABC" com_set = itertools.combinations(s, 2) for i in com_set: print(i)
Комбинации с заменами
В модуле itertools есть еще один метод, который называется комбинациями_with_replacement(). Этот метод также учитывает комбинацию числа с самим собой.
Посмотрим, как это работает.
Для числового набора
import itertools val = [1, 2, 3, 4] com_set = itertools.combinations_with_replacement(val, 2) for i in com_set: print(i)
(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)
Вы можете видеть разницу в выводе выше и выводе для работы нормальной комбинации. Здесь у нас есть такие комбинации, как (1,1) и (2,2), которых нет в обычных комбинациях.
Для строки
import itertools val = "ABCD" com_set = itertools.combinations_with_replacement(val, 2) for i in com_set: print(i)
('A', 'A') ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'B') ('B', 'C') ('B', 'D') ('C', 'C') ('C', 'D') ('D', 'D')