Permutations in Python
The itertools.permutations function accepts a single iterable and creates every possible permutation of input values.
What are permutations
If we have a set of distinct values, for example the set of letters A, B, C, and D, there are different ways we can arrange those items. For example ABCD, CADB, or DCBA. Each unique arrangement…
Перестановки и комбинации в Python
Перестановки и комбинации набора элементов в Python – это различные расположения элементов набора:
- Комбинация – это набор элементов, порядок которых не имеет значения.
- Перестановка – это расположение набора, в котором порядок имеет значение.
Рассмотрим набор как:
Перестановки вышеуказанного набора следующие:
Комбинации вышеуказанного набора, когда два элемента взяты вместе, следующие:
В этом руководстве мы узнаем, как получить перестановки и комбинации группы элементов в Python. Мы рассмотрим наборы символов и цифр.
Мы будем использовать методы combinations() и permutations() в модуле itertools.
Перестановки числовых данных
Чтобы использовать метод permutations() в модуле itertools, нам сначала нужно импортировать модуль.
Теперь давайте определим набор чисел.
Теперь, чтобы получить список перестановок, воспользуемся методом permutations().
Строка кода выше дает объект itertools. Чтобы напечатать различные перестановки, мы будем перебирать этот объект.
Мы получаем результат как:
Полный код этого раздела приведен ниже:
Перестановки строки
Далее мы узнаем, как получить перестановки символов в строке.
Мы будем использовать метод permutations(), но на этот раз мы передадим строку в качестве аргумента.
Перестановки фиксированной длины
Мы можем найти перестановки набора, в котором мы берем только указанное количество элементов в каждой перестановке. Это похоже на nPr в области математики.
Код для поиска перестановок фиксированной длины приведен ниже:
Комбинации числовых данных
Так же, как метод permutations(), мы можем использовать combinations() также в itertools для получения комбинаций набора.
При вызове combinations() нам нужно передать два аргумента: набор для поиска комбинаций и число, обозначающее длину каждой комбинации.
Комбинации строки
Мы также можем получить комбинации строки. Используйте следующий фрагмент кода:
Комбинации с заменами
В модуле itertools есть еще один метод, который называется комбинациями_with_replacement(). Этот метод также учитывает комбинацию числа с самим собой.
Посмотрим, как это работает.
Для числового набора
Вы можете видеть разницу в выводе выше и выводе для работы нормальной комбинации. Здесь у нас есть такие комбинации, как (1,1) и (2,2), которых нет в обычных комбинациях.
Комбинаторика в 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 на русском
Statistics in Python:
Combinations and Permutations
A combination is when you select items from a list and the order doesn’t matter.
A permutation is when you select items from a list and the order does matter.
A poker hand is an example of a combination of cards: an ace-king is the same as a king-ace. The Olympic medallists in an event are an example of a partial permutation of the competitors: the order in which they finish is important as it determines who wins gold, silver and bronze. A complete permutation would be the entire finishing order, ie all the competitors listed in order.
If we select \(k\) things from a total of \(n\) options and we don’t care in what order they are, the total number of combinations (the number of different ways to do this) is:
The total number of distinct 5-card poker hands is \(C(52, 5) = 2,598,960\) .
If we arrange \(n\) things into an order, we will create one of the \(n!\) possible permutations of those items (eg the complete finishing order of a race at the Olympics). If we only select and arrange \(k\) things from a total of \(n\) options in order to create an arrangement (eg the medallists in a race at the Olympics) the number of ways to create a partial permutation like this is:
There are 8 competitors in an Olympic 100m final, meaning that there are \(P(8, 3) = 336\) different possibilities for the podium.
The above assumes that repetition is not allowed, ie a competitor cannot win more than one medal. If repetition is allowed, for example if you look at the top 3 fastest 100m times that have ever been run by these 8 athletes, the possible number of arrangements is \(n^k\) , ie \(8^3 = 512\) . Another example of arrangement with repetition is if you are creating words from an alphabet: the total number of three-letter words is \(26\times26\times26=17,576\) .
1 Calculating Combinations and Permutations
The built-in module math in Python provides the factorial() , comb() and perm() functions which can be used as follows:
1.1 Combinations
How many distinct 5-card poker hands are possible?
1.2 Permutations
An Olympic 100m final has 8 competitors. How many possible finishing orders are there?
How many different possible podiums (gold, silver and bronze winners) are there?
If we look up the top 3 all-time fastest runs by these 8 athletes how many arrangements could we possibly see?
2 Creating Combinations and Permutations
It’s all good and well knowing how many combinations and/or permutations there are, but how can we see what they are? The built-in itertools module in Python has the combinations and permutations functions which can be used as follows:
2.1 Combinations
On 26 July 2021 the top 4 ranked rugby teams in the world were:
- South Africa
- New Zealand
- England
- Ireland
If we wanted to organise a round-robin tournament where each team played each other once, we could create combinations of two teams:
2.2 Permutations
If we wanted to create a double round-robin tournament where each team played each other twice — ie once at home and once away — we could create permutations of two teams: