Combinations code in 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')

Источник

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

Источник

Combinations in Python

If you want to see how to create combinations without itertools in Python, jump to this section.

Combinations

A combination is a selection of elements from a set such that order doesn’t matter. Say we have a list [1, 2, 3] , the 2-combinations of this set are [(1, 2), (1, 3), (2, 3)] . Notice that order doesn’t matter. Once we have (1, 2) in the set, we don’t also get (2, 1) . By default, combinations are typically defined to be without replacement. This means that we’ll never see (1, 1) – once the 1 has been drawn it is not replaced.

You can also have combinations with replacement. The 2-combinations (with replacement) of the list [1, 2, 3] are [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)] . In this case, numbers are replaced after they’re drawn.

There’s one important note before we jump into implementations of this operation in Python. The combinations API from itertools treats list index as the element being drawn. This means any iterable can be treated like a set (since all indices are unique). But it’s important to realize that if you pass in [1, 1, 2] , the elements will not be de-duped for you. The 2-combinations of [1, 1, 2] according to the itertools combinations API is [(1, 1), (1, 2), (1, 2)] .

Approaches

Combinations in itertools

It’s extremely easy to generate combinations in Python with itertools. The following generates all 2-combinations of the list [1, 2, 3] :

import itertools sequence = [1, 2, 3] itertools.combinations(sequence, 2) # Expected result #

The combinations() function returns an iterator. This is what you want if you plan to loop through the combinations. But you can convert it into a list if you want all the combinations in memory:

list(itertools.combinations(sequence, 2)) # Expected result # [(1, 2), (1, 3), (2, 3)]

A useful property of the combinations() function is that it takes any iterable as the first argument. This means you can pass lazy sequences[1] in:

list(itertools.combinations(range(3), 2)) # Expected result # [(0, 1), (0, 2), (1, 2)]

Combinations with replacement in itertools

It’s also very easy to generate combinations with replacement:

list(itertools.combinations_with_replacement(sequence, 2)) # Expected result # [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

The interface for combinations_with_replacement() is the same as combinations() .

Combinations without itertools

Once in a while, you might want to generate combinations without using itertools. Maybe you want to change the API slightly — say, returning a list instead of an iterator, or you might want to operate on a NumPy array.

Under the hood, Python uses a C implementation of the combinations algorithm. But the documentation provides a helpful Python implementation you can use, reproduced here for convenience:

def combinations(iterable, r): # combinations('ABCD', 2) --> AB AC AD BC BD CD # combinations(range(4), 3) --> 012 013 023 123 pool = tuple(iterable) n = len(pool) if r > n: return indices = list(range(r)) yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != i + n - r: break else: return indices[i] += 1 for j in range(i+1, r): indices[j] = indices[j-1] + 1 yield tuple(pool[i] for i in indices)

Combinations without replacement (and without itertools)

The Python docs also give us a Python-only implementation of combinations_with_replacement() :

def combinations_with_replacement(iterable, r): # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC pool = tuple(iterable) n = len(pool) if not n and r: return indices = [0] * r yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != n - 1: break else: return indices[i:] = [indices[i] + 1] * (r - i) yield tuple(pool[i] for i in indices)

Источник