Суммы, перестановки и сочетания: считаем, не перебирая

Если ты без перебора скажешь, сколько пар у тысячи элементов и почему подмножеств у n элементов 2ⁿ, листай до «Теперь сам» в конце.

Как думаешь, сколько сравнений

Программа сравнивает каждого из 1000 пользователей с каждым, чтобы найти дубликаты: for i in range(n), внутри for j in range(i + 1, n). Сколько сравнений она сделает? Ответь себе до того, как читать дальше. Миллион? Полмиллиона? Ровно? Спросить можно и иначе: сколько разных пар можно составить из тысячи человек? Ответ на оба вопроса один, и урок о том, почему.

На что это похоже

Рукопожатия на встрече. Каждый из n гостей жмёт руку каждому другому. Если считать «каждый жмёт n - 1 рук», получится n(n - 1), но каждое рукопожатие посчитано дважды - его видят оба участника. Делим на два. Комбинаторика почти вся такая: посчитать прямолинейно, а потом понять, сколько раз каждое посчитано, и поделить.

Механизм: две суммы и правило произведения

Арифметическая сумма. Сложим 1 + 2 + ... + 100 по-хитрому: первое с последним, второе с предпоследним - 1 + 100, 2 + 99, ... Каждая пара даёт 101, пар 50, итого 5050. Для любого n, в том числе нечётного, надёжнее сложить сумму с ней же, записанной задом наперёд: n столбиков по n + 1, то есть удвоенная сумма равна n(n + 1). В общем виде 1 + 2 + ... + n = n(n + 1)/2, а сумма без последнего, 0 + 1 + ... + (n - 1) = n(n - 1)/2. Короткая запись суммы - Σ: Σ i при i от 1 до n значит «сложить все i от 1 до n».

Сумма удвоений. 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1. Видно на двоичной записи: справа k + 1 единиц подряд, а это на единицу меньше, чем 1 с k + 1 нулём. Следствие, которое понадобится много раз: в ряду удвоений последнее слагаемое больше суммы всех предыдущих. Поэтому массив, который при переполнении удваивается, на все переносы тратит меньше, чем 2n: пока он дорос до n элементов, он переезжал при размерах 1, 2, 4, ..., 2^k, где 2^k < n, и каждый раз копировал всё содержимое - всего 1 + 2 + ... + 2^k = 2^(k+1) - 1 < 2n переносов.

Правило произведения. Если первый выбор можно сделать a способами, а второй (при любом первом) - b способами, то пару выборов - a · b способами. Из него выводится всё остальное:

Факториал n! - произведение всех чисел от 1 до n, причём 0! = 1 (пустой набор упорядочить можно одним способом). Растёт он быстрее экспоненты: 10! = 3 628 800, 20! - около 2.4 · 10^18.

Правило

1 + ... + n = n(n + 1)/2; 1 + 2 + ... + 2^k = 2^(k+1) - 1. Независимые выборы перемножаются. Порядков n вещей - n!, подмножеств - 2ⁿ, наборов из k без порядка - C(n, k), пар - n(n - 1)/2. Если считал с повторами, дели на число повторов каждого варианта.

Разбор: формулы против перебора

Проверим формулы прямым перебором на пяти элементах - модуль itertools честно выписывает все варианты:

from itertools import combinations, permutations, product
from math import comb, factorial

n = 5
elementy = list(range(n))
print(len(list(permutations(elementy))), factorial(n))
print(len(list(combinations(elementy, 2))), comb(n, 2), n * (n - 1) // 2)
print(len(list(product([0, 1], repeat=n))), 2 ** n)
print(sum(range(1, 101)), 100 * 101 // 2)
print(sum(2 ** i for i in range(11)), 2 ** 11 - 1)
print(factorial(10), factorial(20))

120 120
10 10 10
32 32
5050 5050
2047 2047
3628800 2432902008176640000

product([0, 1], repeat=n) выписывает все строки длины n, где на каждой позиции 0 или 1. Запись sum(2 ** i for i in range(11)) значит «сумма 2 ** i по всем i от 0 до 10»: конструкция выражение for x in ... внутри скобок вызова выдаёт значения по одному. Все пары совпали. Сами permutations и combinations пригодятся в разделе про перебор, а здесь важнее формулы: они отвечают на вопрос «сколько» без выписывания, и на n = 50 выписывание уже невозможно.

Разбор: цикл, который считает пары

Вернёмся к вопросу из начала. Внутренний цикл на круге i делает n - 1 - i сравнений: 999, потом 998, ..., потом 0. Сумма 0 + 1 + ... + 999 = 1000 · 999 / 2 = 499 500. И это ровно C(1000, 2): программа сравнивает каждую пару по одному разу. Если написать внутренний цикл for j in range(n) с проверкой i != j, сравнений станет n(n - 1) = 999 000 - каждая пара дважды, как рукопожатие, посчитанное обоими.

Так же считается любой цикл, внутренний проход которого растёт или убывает на единицу: сумма арифметическая, и её старшая часть - n²/2: n(n - 1)/2 = n²/2 - n/2, и на больших n слагаемое n/2 ничтожно рядом с n²/2. Именно поэтому «квадратичный алгоритм» - это не обязательно два цикла по n: проверка x in spisok сама проходит список подряд, и одного цикла с такой проверкой по растущему списку достаточно.

Что ломается без этого

Перебор всех порядков кажется безобидным, пока элементов мало: 8 городов - 40 320 маршрутов, это мгновенно; 15 городов - больше триллиона; 20 - два с половиной квинтиллиона. Программа, отлаженная на восьми, не закончится на двадцати. Вторая ошибка - считать упорядоченные пары там, где нужны неупорядоченные, и получить ответ ровно вдвое больше: задача главы ловит именно это. Третья - вычислять C(n, k) через три факториала на больших числах: в Python это верно, но медленно, а в языке с ограниченными целыми 20! уже на грани переполнения 64 бит.

Зачем это в работе

Прикинуть, можно ли перебрать. Пароль из восьми строчных латинских букв - 26^8, около 200 миллиардов вариантов, это часы на видеокарте; из двенадцати - уже много лет. Тестовых комбинаций для десяти флажков настройки - 1024, их можно прогнать все; для сорока - нет, и нужен другой подход. Сколько пар сравнить при поиске дубликатов среди миллиона записей - полтриллиона, значит, нужна сортировка или хеш. Каждая такая прикидка - одна строка из таблицы выше.

Теперь сам

Сколько сравнений сделает «для каждой пары i < j проверить, равны ли a[i] и a[j]» на 2000 элементах? И сколько способов выбрать команду из 3 человек среди 10?