Комбинаторика в 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. Сколько существует способов выбрать k конфет из n без учета порядка? Ответ прост, в начале найдем размещение из n по k без повторений, но тогда одинаковые наборы конфет, имеющие разный порядок их следования будут повторяться. Сколько существует способов переставить k конфет? Правильно, перестановка из k элементов без повторений. Итоговый ответ: размещения из n по k делим на перестановки из 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
Исходя из второго вызова заметим, что одинаковые элементы, стоящие на разных позициях, считаются разными.
Пример 2
Размещение отличается от перестановки ограничением на количество доступных ячеек
Пример 3
C помощью размещений с повторениями можно легко перебрать все строки фиксированной длины, состоящие из заданных символов
Пример 4
С помощью сочетаний без повторений можно перебрать все наборы не повторяющихся букв из заданной строки, массива или другого итерируемого объекта без учета порядка
Пример 5
Результат аналогичен вызову combinations, но в результат также добавлены множества с одинаковыми элементами.
Материалы:
Н.В. Горбачев «Сборник олимпиадных задач по математике»
Документация по python на русском
Поиск комбинаций в Python без использования itertools
Есть много случаев, когда нам нужно найти разные комбинации из одной строки или другого набора чисел. Чтобы найти такие комбинации в Python, у нас есть модуль itertools, наиболее распространенный для поиска различных комбинаций и перестановок.
Этот модуль очень эффективен и работает очень быстро, чтобы найти все возможные комбинации. Но функции модуля itertools – не единственный возможный метод, который мы можем использовать для поиска комбинаций.
В этом руководстве мы узнаем о различных методах, с помощью которых мы можем осуществить поиск различных комбинаций из строки в Python без использования itertools.
Комбинации в Python без использования itertools
В этом разделе мы напишем программы Python для поиска комбинаций, реализовав в них несколько методов. В нашей программе на Python мы будем использовать следующие методы:
- итерационный метод;
- метод рекурсии.
В обоих методах сначала мы посмотрим на программу и поймем, что она работает, а затем перейдем к объяснительной части, чтобы понять используемую в ней реализацию.
Поиск с помощью метода итерации
Чтобы реализовать итеративный подход в программе, мы должны импортировать библиотеку numpy, чтобы использовать ее функции.
Мы использовали метод итерации в приведенной выше программе, чтобы найти комбинации из входной строки.
Во-первых, мы использовали функцию Python по умолчанию с входной строкой и длиной комбинационного набора в качестве параметра. Затем мы преобразовали входную строку в кортеж. Также мы проверили, не превышает ли требуемая длина комбинации длину строки.
После этого мы использовали функцию order() numpy, чтобы установить индекс для кортежа. Мы собираемся перебирать кортеж с индексной переменной.
Затем мы перебирали кортеж, используя обратный цикл for и еще один цикл for внутри цикла while. После итерации в циклах мы получили возможные комбинации нужной длины.
Затем мы взяли строку ввода от пользователя. В последнем действии мы вернули комбинации трех наборов из входной строки.
Использование метода рекурсии
В подходе рекурсивного метода мы будем перебирать список, состоящий из списка строк. Давайте разберем это в следующем примере:
В приведенной выше программе при реализации рекурсивного подхода мы не использовали какой-либо конкретный модуль Python. Как и метод итерации, мы использовали функцию по умолчанию для реализации метода рекурсии в коде.
В этой программе мы использовали условие, чтобы проверить, требуется ли длина комбинации. Затем мы использовали метод рекурсии внутри функции с циклом for. После использования метода рекурсии мы возвращали комбинации необходимой длины из входной строки. Наконец, мы взяли строку в качестве ввода от пользователя и вернули на выходе комбинации из трех наборов.
Получаем все возможные комбинации из n элементов списка
Итак, нам необходимо вывести все вариации n элементов в некотором списке. Будем считать комбинации вида [a, b, c] и [c, b, a] одинаковыми.
С этой задачей справится модуль itertools и его функция combinations:
Английский для программистов
Наш телеграм канал с тестами по английскому языку для программистов. Английский это часть карьеры программиста. Поэтому полезно заняться им уже сейчас