Комбинаторика в программировании: перебор вариантов без хаоса

Комбинаторика отвечает на вопрос, сколько вариантов возможно и как их перебрать. В программировании для школьников она встречается в задачах на пароли, расписания, команды,…

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

Простой полный перебор подходит, когда вариантов немного.

alphabet = 'ABC'

for first in alphabet:
    for second in alphabet:
        print(first + second)

Эта программа выводит все двухбуквенные коды из трех символов. Всего вариантов 3 * 3 = 9.

Перебор с условием

Часто нужно не вывести все варианты, а посчитать подходящие.

digits = '0123456789'
count = 0

for a in digits:
    for b in digits:
        number = int(a + b)

        if number % 4 == 0:
            count += 1

print(count)

Здесь перебираются все двузначные записи с ведущим нулем. Важно внимательно читать условие: иногда 04 допустимо как код, а иногда число должно быть именно двузначным.

Как оценить число вариантов

Перед программированием посчитайте, сколько вариантов получится. Если три позиции и десять цифр, это 1000 вариантов. Если десять позиций и десять цифр, это уже 10 миллиардов, полный перебор не подойдет.

Полезные вопросы

1. Можно ли повторять элементы?
2. Важен ли порядок?
3. Нужно ли выбрать все элементы или только часть?
4. Есть ли ограничения, которые можно проверить раньше?

Комбинаторные задачи учат дисциплине. Чем раньше школьник выпишет правила вариантов, тем меньше риск написать хаотичный перебор и получить неверный ответ на ОГЭ, ЕГЭ или олимпиаде.