Python все возможные комбинации элементов

Комбинаторика в 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 cc

C помощью размещений с повторениями можно легко перебрать все строки фиксированной длины, состоящие из заданных символов

Пример 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 — это использовать модуль itertools и входящую в него функциию permutations() .

Почему стоит использовать модуль itertools?

Модуль itertools содержит функции, упрощающие работу с итераторами. Основное преимущество этого модуля заключается в эффективном использовании памяти, что позволяет получить нужный результат за минимальное время.

Синтаксис функции permutations()

import itertools itertools.permutations(lst, length = None)

Параметрами функции являются:

• lst — это итерируемая последовательность (например: список, кортеж, строка)
• lengh — это длина возвращаемых кортежей (необязательный параметр). Если length = None , то для перестановок будут использоваться все элементы итератора.

Ниже мы рассмотрим варианты получения всех возможных перестановок для списка и строки:

Код для получения всех комбинаций элементов в Python (длина комбинаций = числу элементов)

1. Получим все перестановки элементов списка lst = [1, 2, 3]:

import itertools nums = [1, 2, 3] permutations = list(itertools.permutations(nums)) print(permutations)

Вывод на экран:

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

В рассматриваемой задаче мы получаем комбинации, содержащие все элементы списка, поэтому можно не указывать значение второго аргумента для функции permutations().

2. Получим все возможные сочетания букв в слове «кот»:

import itertools word = "кот" # получим списки из перестановок букв letters = list(itertools.permutations(word)) # объединим списки с буквами в слова permutations = [ ''.join(i) for i in letters ] print(permutations)

Вывод на экран:

Пояснения к коду:

С помощью кода list(itertools.permutations(word)) мы получаем список с кортежами из букв «к», «о» и «т», расположенных в разном порядке:

letters = [('к', 'о', 'т'), ('к', 'т', 'о'), ('о', 'к', 'т'), ('о', 'т', 'к'), ('т', 'к', 'о'), ('т', 'о', 'к')].

Так как мы получаем комбинации, содержащие все три буквы слова «кот», значение второго аргумента для функции permutations() можно не указывать. Теперь чтобы объединить кортежи из букв в слова, для каждого кортежа i из списка letters вызовем метод ».join(i) , объединяющий кортеж в строку. Вместо генератора списков permutations = [ ».join(i) for i in letters ] можно организовать перебор элементов списка letters с помощью цикла for. Это также рабочий способ, хоть и более динный:

import itertools word = "кот" # получим списки из перестановок букв letters = list(itertools.permutations(word)) permutations = [] for i in letters: permutations.append(''.join(i)) print(permutations)

Вывод на экран:

Код для получения комбинаций из n элементов: (длина комбинаций lst , то в качестве второго аргумента функции permutation() мы передаем значение 2.

2. Получим сочетания из двух букв слова «кот»:

import itertools word = "кот" letters = list(itertools.permutations(word, 2)) res = [''.join(i) for i in letters] print(res)

Вывод на экран:

Пояснения к коду:

Так как мы получаем комбинации двух букв слова «кот», то в качестве второго аргумента функции permutations() передаем значение 2.

В результате выполнения кода: list(itertools.permutations(word, 2)) мы получим список letters, состоящий из кортежей: [(‘к’, ‘о’), (‘к’, ‘т’), (‘о’, ‘к’), (‘о’, ‘т’), (‘т’, ‘к’), (‘т’, ‘о’)] . После этого мы объединяем элементы кортежей в строки с помощью метода ».join(i) . Метод join() будем вызывать для каждого кортежа, входящего в letters. Объединение букв — элементов кортежей можно также организовать в цикле for. Тогда код будет выглядеть немного иначе:

import itertools word = "кот" letters = itertools.permutations(word, 2) res = [] for i in letters: res.append(''.join(i)) print(res)

Вывод на экран:

У нас появился Telegram-канал для изучающих Python! Присоединяйтесь: вместе «питонить» веселее! 😉 Ссылка на канал: «Кодим на Python!»

Источник