Комбинаторика в Python. Простой пример

Настоящие профессионалы работают с любым материалом. Если дана задача — мы её выполним. Если уж совсем откровенно, то для этого нужно просто следовать нашим советам

Комбина…что?

Комбинаторика — это раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого множества в соответствии с заданными правилами. Используется эта штука в информатике, применялась при разработке сетевых протоколов динамической маршрутизации (OSPF) и оптимизации распределения трафика в сетях. Мелькает в криптографии и проверке статистических гипотез

Зачем нам itertools

Это стандартная библиотека, которая позволяет некоторые последовательности объектов и управлять ими при помощи итераций, формируя их через циклы, массивы и генераторы списков. Как раз то, что нам нужно для решения задач по комбинаторике

Задача:

В новую школу не успели завезти парты в один из классов. Поэтому в этот класс принесли круглые столы из столовой. Столы в столовой разных размеров — на 4, 7 и 13 человек, всего их хватало на 59 человек. Когда часть столов отнесли в класс, в столовой осталось 33 места. Сколько столов отнесли в класс? Объясните ваш ответ.

Решение

1. Для начала посчитаем количество мест, задействованных в классе: 59-33 = 26. Такое число можно собрать разными способами — в этом и суть задачи
2. Нам нужно получить все возможные суммы из столов разных размеров (4,7,13), таким образом, чтобы на выходе получилось 26. Зададим этот параметр переменной target
3. Так как у нас столы могут повторятся (ну т.е. мы можем взять два на 4 , один на 7 и т.п.), то в список tables надо бить все вариации, которые могут получить в сумме число близкое к 26 (4+4+4+4+4 = 24, 7+7+7 = 21, 13+13 =26)
4. Прогоняем по вложенным циклам, результат (список) записываем в переменную result. Обратите внимание на первый цикл. Функция range() принимает один обязательный и два необязательных аргумента (старт, стоп, шаг). Стартом у нас будет длина списка tables, стоп будет нулем, шаг -1. Шаг может быть как положительным, так и отрицательным (но не может быть равен нулю)
5. Касаемо itertools.combinations(tables, i) — так мы задаем комбинации длиной i из tables без повторяющихся элементов.
6. Задаем переменную unique_value для вывода списка уникальных множеств. Конструкция list(set(some_list)) хорошо подходит для удаления дубликатов
7. >> [(4, 4, 4, 7, 7), (13, 13)]

import itertools
tables = [4,4,4,4,4,7,7,7,13,13]
target = 26
result = [seq for i in range(len(tables), 0, -1)
          for seq in itertools.combinations(tables, i)
          if sum(seq) == target]
unique_value = list(set(result))
print(unique_value)

Скачать ноутбук (Google Colab)