Перебор вариантов и приёмы оптимизации
Когда умного решения не видно — перебираем все варианты; но делаем это с умом, чтобы успеть.
Полный перебор (brute force) — метод решения, при котором проверяются все возможные варианты, и среди них выбирается подходящий.
Зачем это нужно
Перебор — честный и универсальный способ: если можно перечислить все варианты, можно найти ответ. Он спасает там, где формулу вывести трудно: найти все пары с заданной суммой, перебрать комбинации, решить задачу подбором. Но у перебора есть враг — комбинаторный взрыв: число вариантов растёт так быстро, что наивный перебор «не успевает». Этот урок учит и перебирать, и понимать, где перебор бессилен, и как его ускорить отсечениями.
У перебора особая роль в арсенале программиста — это «решение по умолчанию», к которому всегда можно отступить. Когда вы не видите хитрого приёма, но способны перечислить все возможные ответы и проверить каждый, задача уже решена — пусть и не самым быстрым способом. Это придаёт уверенности: безвыходных задач становится меньше. Но здесь же кроется главный урок темы — чувство меры. Перебор хорош, пока вариантов умеренно много; стоит их числу начать расти как 2ⁿ или n!, и даже самый быстрый компьютер захлебнётся задолго до ответа. Поэтому грамотный подход двухступенчатый: сначала прикинуть, сколько вариантов придётся проверить, и лишь убедившись, что их обозримое количество, запускать перебор; в противном случае — искать умный алгоритм или способ отсечь заведомо безнадёжные ветви. Умение оценить размер перебора до его запуска и есть та зрелость, которую вырабатывает этот урок.
Простейший перебор: найти подходящее число
Иногда достаточно перебрать диапазон и проверить условие. Найдём все трёхзначные числа, у которых сумма цифр равна 7 и которые делятся на 7 — задача, где формулу искать дольше, чем перебрать:
def digit_sum(n):
return sum(int(c) for c in str(n))
result = []
for n in range(100, 1000):
if digit_sum(n) == 7 and n % 7 == 0:
result.append(n)
print("найдено чисел:", len(result))
print("наименьшее:", result[0], " наибольшее:", result[-1])
print("все:", result)Вывод:
найдено чисел: 4 наименьшее: 133 наибольшее: 700 все: [133, 322, 511, 700]
Вложенный перебор: все пары
Чтобы перебрать пары элементов, нужны два вложенных цикла. Классическая задача: найти, сколько пар чисел в списке дают в сумме заданное значение. Наивный перебор пар — это O(n²):
data = [2, 7, 11, 15, 4, 3, 8]
target = 11
pairs = []
for i in range(len(data)):
for j in range(i + 1, len(data)): # j > i, чтобы не считать пару дважды
if data[i] + data[j] == target:
pairs.append((data[i], data[j]))
print("пары с суммой", target, ":", pairs)
print("количество:", len(pairs))Вывод:
пары с суммой 11 : [(7, 4), (3, 8)] количество: 2
Оптимизация: тот же результат за O(n)
Часто квадратичный перебор можно ускорить с помощью множества. Для задачи о парах: проходя по числам, проверяем, встречали ли мы уже «дополнение» до целевой суммы. Это превращает O(n²) в O(n) — наглядный пример, что структура данных меняет сложность:
data = [2, 7, 11, 15, 4, 3, 8]
target = 11
seen = set()
count = 0
for x in data:
need = target - x # какое число дополнит x до target
if need in seen: # проверка в множестве — почти мгновенна
count += 1
seen.add(x)
print("пар с суммой", target, ":", count)Вывод:
пар с суммой 11 : 2
Комбинаторный взрыв: где перебор бессилен
Полный перебор хорош, пока вариантов немного. Но их число растёт пугающе быстро: число подмножеств множества из n элементов равно 2ⁿ, число перестановок — n!. Покажем, насколько быстро «взрывается» задача:
import math
print(f"{'n':>3} | {'подмножеств 2^n':>16} | {'перестановок n!':>18}")
print("-" * 44)
for n in (5, 10, 20, 30):
print(f"{n:>3} | {2**n:>16} | {math.factorial(n):>18}")Вывод:
n | подмножеств 2^n | перестановок n! -------------------------------------------- 5 | 32 | 120 10 | 1024 | 3628800 20 | 1048576 | 2432902008176640000 30 | 1073741824 | 265252859812191058636308480000000
Для 30 элементов перестановок больше, чем атомов в обозримой Вселенной. Вывод: для больших n нужен умный алгоритм, а не перебор.
Перебор с отсечением и itertools
Когда перебор всё же нужен, его ускоряют отсечением: как только частичное решение становится безнадёжным, его не продолжают. А стандартный модуль itertools аккуратно генерирует комбинации и перестановки, не загружая всё в память сразу. Переберём все способы выбрать 2 предмета из 4:
from itertools import combinations, permutations
subjects = ["матем", "физика", "информ", "химия"]
print("Сочетания по 2 (порядок не важен):")
for combo in combinations(subjects, 2):
print(" ", combo)
print("Перестановок из 3 первых:", len(list(permutations(subjects[:3]))))Вывод:
Сочетания по 2 (порядок не важен):
('матем', 'физика')
('матем', 'информ')
('матем', 'химия')
('физика', 'информ')
('физика', 'химия')
('информ', 'химия')
Перестановок из 3 первых: 6
Попробуй сам
Решим задачу подбором: найти все способы разменять 20 рублей монетами по 1, 2, 5 и 10. Это перебор с отсечением — мы не берём больше монет, чем влезает в сумму.
amount = 20
ways = 0
for ten in range(amount // 10 + 1):
for five in range((amount - 10*ten) // 5 + 1):
for two in range((amount - 10*ten - 5*five) // 2 + 1):
rest = amount - 10*ten - 5*five - 2*two
# остаток добираем монетами по 1 — всегда ровно один способ
ways += 1
print("способов разменять 20 руб:", ways)Вывод:
способов разменять 20 руб: 40
Частые ошибки
- Считают пары дважды. Во внутреннем цикле начинайте с
j = i + 1, иначе пара (a, b) посчитается и как (b, a). - Запускают полный перебор на больших n. 2ⁿ и n! растут чудовищно; для больших данных перебор не успеет.
- Не используют отсечение. Если частичный вариант уже превысил лимит — нет смысла его достраивать.
- Забывают, что множество ускоряет проверку. Замена «есть ли в списке» на «есть ли в множестве» часто превращает O(n²) в O(n).
Итоги
- Полный перебор универсален: перечислить все варианты и выбрать подходящий.
- Вложенные циклы перебирают пары за O(n²); часто это ускоряется множеством до O(n).
- Число вариантов растёт как 2ⁿ (подмножества) и n! (перестановки) — для больших n перебор бессилен.
itertoolsаккуратно генерирует сочетания и перестановки; отсечение ускоряет перебор.
