В 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() принимает аргумент string и предоставляет объект itertools . Если мы попробуем напечатать перестановки напрямую, мы получим следующее:
Выход: <itertools.permutations object at 0x0000019138C87630>
Поэтому необходимо запускать цикл для печати каждой записи.
Перестановки с повторениями 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
 |
Пример 7.
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 |