Размещения с повторениями python

В Python есть достаточно много стандартных встроенных библиотек. Модуль itertools – инструмент стандартной библиотеки Python, содержащей распространённые шаблоны итераторов. Итератор — это объект, который позволяет перемещаться (итерироваться) по элементам некоторой последовательности. Он не хранит все значения сразу, а позволяет последовательно пройти по ним в цикле.

Для сохранения всех значений итератора его можно преобразовать в список с помощью функции list().

Модуль itertools позволяет решать программные задачи, построенные на структурах комбинаторики. Рассмотрим из них некоторые полезные функции.

Перестановки permutations (iterable)

Возвращает последовательные k перестановок элементов в итерируемом объекте iterable. Элементы рассматриваются как уникальные в зависимости от их позиции, а не от их значения. Таким образом, если входные элементы уникальны, то в каждой перестановке не будет повторяющихся значений.

Пример 1. Дано: множество ягод. Найти все перестановки ягод в множестве и вывести их количество.

import itertools
berries = [‘клубника’,’вишня’,’ежевика’]
for b in itertools.permutations (berries):
print(*b)
print(‘Всего перестановок:’, len(list(itertools.permutations (berries))))

Выход:
клубника вишня ежевика
клубника ежевика вишня
вишня клубника ежевика
вишня ежевика клубника
ежевика клубника вишня
ежевика вишня клубника
Всего перестановок: 6

Пример 2. Вывести все перестановки слова ‘ ABC ’

import itertools
st = ‘ABC’
per = itertools.permutations (st)
for s in per:
print(*s)

Выход :
A B C
A C B
B A C
B C A
C A B
C B A

Функция permutations() принимает аргумент s tring и предоставляет объект itertools . Если мы попробуем напечатать перестановки напрямую, мы получим следующее:

Поэтому необходимо запускать цикл для печати каждой записи.

Перестановки с повторениями permutations (iterable)

Пример 3 . Алексей занимается спортом. 4 раза в неделю — легкой атлетикой, 2 раза в неделю силовыми упражнениями и один день отдыхает. Сколькими способами он может составить себе расписание на неделю?

import itertools
sport = ‘ ллллссо ‘
rasp = list(itertools.permutations (sport))
print(‘Всего перестановок с повторениями:’, len(set(rasp))) # преобразуя список в множество мы убираем дублирующиеся строки

Выход:
Всего перестановок с повторениями: 105

Сочетания combinations (iterable , k )

Сочетания по k элементов – выбранные из множества iterable объектов комбинации k объектов, отличающиеся хотя бы одним объектом. Сочетания различаются только элементами, порядок их не важен: ab и ba – это одно и тоже сочетание.

Пример 4. Составить сочетания из трех ягод по два и вывести их количество.

import itertools
berries = [‘клубника’,’вишня’,’ежевика’]
for c in itertools.combinations (berries, 2):
print(*c)
print(‘Всего сочетаний:’, len(list(itertools.combinations (berries, 2))))

Выход:
клубника вишня
клубника ежевика
вишня ежевика
Всего сочетаний: 3

Пример 5: Составить трёхцветный флаг из четырех цветов.

import itertools
colors = [‘белый’, ‘жёлтый’, ‘синий’, ‘красный’]
for flag in itertools.combinations (colors, 3):
print (* flag )
print (‘Всего сочетаний: ‘, len (list (itertools.combinations (colors, 3))))

Выход:
белый жёлтый синий
белый жёлтый красный
белый синий красный
жёлтый синий красный
Всего сочетаний: 4

Порядок следования не имеет значения, поэтому все тройки цветов уникальны.

Сочетания с повторениями combinations_with_replacement (iterable, k)

Пример 6. Сколько существует способов выбрать с повторениями из трех ягод по две?

import itertools
berries = [‘клубника’,’вишня’,’ежевика’]
for c in itertools.combinations_with_replacement (berries,2):
print(*c)
print(‘ Всего сочетаний с повторениями :’, len (list (itertools.combinations_with_replacement (berries,2))))

Выход:
клубника клубника
клубника вишня
клубника ежевика
вишня вишня
вишня ежевика
ежевика ежевика
Всего сочетаний с повторениями: 6

import itertools
letters = ‘ABCD’
code_vars = itertools.combinations_with_replacement (letters, 2)
for var in code_vars:
print(*var)
print(‘Всего сочетаний с повторениями: ‘, len (list (itertools.combinations (colors, 3))))

Выход:
A A A
A A B
A A C
A A D
A B B
A B C
A B D
A C C
A C D
A D D
B B B
B B C
B B D
B C C
B C D
B D D
C C C
C C D
C D D
D D D
Всего сочетаний с повторениями: 20

Размещения permutations (iterable, k)

Размещения из n элементов по k (k≤n) – любое множество, состоящее из k элементов, взятых в определённом порядке из данных iterable элементов. Это те же сочетания, для которых важен порядок следования элементов.

Пример 8. Составить все размещения ягод из трех по две.

import itertools
berries = [‘клубника’,’вишня’,’ежевика’]for r in itertools.permutations (berries, 2):
print(*r)
print(‘Всего размещений:’, len (list (itertools.permutations (berries, 2))))

Выход:
клубника вишня
клубника ежевика
вишня клубника
вишня ежевика
ежевика клубника
ежевика вишня
Всего размещений: 6

Пример 9. Составить флаг с учётом порядка следования цветов.

import itertools
colors = [‘белый’, ‘жёлтый’, ‘синий’, ‘красный’]
for flag in itertools.permutations (colors, 3):
print (*flag)
print(‘Всего размещений:’, len(list(itertools.permutations (colors, 3))))

Выход :
белый жёлтый синий
белый жёлтый красный
белый синий жёлтый
белый синий красный
белый красный жёлтый
белый красный синий
жёлтый белый синий
жёлтый белый красный
жёлтый синий белый
жёлтый синий красный
жёлтый красный белый
жёлтый красный синий
синий белый жёлтый
синий белый красный
синий жёлтый белый
синий жёлтый красный
синий красный белый
синий красный жёлтый
красный белый жёлтый
красный белый синий
красный жёлтый белый
красный жёлтый синий
красный синий белый
красный синий жёлтый
Всего размещений: 24

Размещение с повторениями product ()

Размещение с повторениями (выборка с возвращением) – это комбинаторное размещение объектов, в котором каждый объект может участвовать в размещении несколько раз.

Пример 10. Составить все размещения с повторениями из ягод из трех по две.

import itertools
berries = [‘клубника’,’вишня’,’ежевика’]for rr in itertools.product (berries, repeat = 3):
print (*rr)
print(‘Всего размещений c повторениями:’, len (list (itertools.product (berries, repeat = 3))))

Выход:
клубника клубника клубника
клубника клубника вишня
клубника клубника ежевика
клубника вишня клубника
клубника вишня вишня
клубника вишня ежевика
клубника ежевика клубника
клубника ежевика вишня
клубника ежевика ежевика
вишня клубника клубника
вишня клубника вишня
вишня клубника ежевика
вишня вишня клубника
вишня вишня вишня
вишня вишня ежевика
вишня ежевика клубника
вишня ежевика вишня
вишня ежевика ежевика
ежевика клубника клубника
ежевика клубника вишня
ежевика клубника ежевика
ежевика вишня клубника
ежевика вишня вишня
ежевика вишня ежевика
ежевика ежевика клубника
ежевика ежевика вишня
ежевика ежевика ежевика
Всего размещений c повторениями: 27

Пример 11. Составить пин-код из четырех цифр. На каждой позиции стоит цифра от 0 до 9. Позиции не зависят друг от друга.

import itertools
digits = range(10)
pincode = itertools.product(digits, repeat=4)
for pin in pincode:
print (*pin)
print (‘Всего размещений с повторениями:’, len (list (itertools.product (digits, repeat=4))))

0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
.
9 9 9 7
9 9 9 8
9 9 9 9
Всего размещений с повторениями: 10000

Пример 12. Отличительные особенности функций

product(‘ABCD’, repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations(‘ABCD’, 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations(‘ABCD’, 2)	AB AC AD BC BD CD
combinations_with_replacement(‘ABCD’, 2)	AA AB AC AD BB BC BD CC CD DD

Источник

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

Источник