Счёт без перебора

Любой вопрос о подсчёте — это на самом деле вопрос о том, сколько ответов у процедуры принятия решений. Один способ отвечать на такие вопросы вы уже знаете: написать цикл, перебрать, посмотреть на вывод. Он работает, пока вывод невелик, а потом перестаёт работать полностью, а не постепенно. Этот урок о том, как получить число, ни разу не построив список.

/* multiplication rule */

  3 starters * 4 mains * 2 desserts  =  24

  plate: 4 letters, 3 digits
  26^4          = 456976
  26^4 * 10^3   = 456976000

  /* addition rule */
  12 routes + 7 routes  =  19 routes

Правило умножения — основа, и оно действительно настолько простое: если первый выбор можно сделать a способами, а после него второй — b способами, то пару можно сделать a умножить на b способами. Два правила удерживают его от ошибок. Умножайте, когда выборы идут последовательно; складывайте, когда это альтернативы, которые никогда не случаются вместе. Почти каждая ошибка в подсчёте — это одно из этих двух правил, применённое там, где нужно было другое.

/* ordered choice: pile of 10 people, 3 different prizes */

10 choices, then 9, then 8

  P(10, 3)  =  10 * 9 * 8
            =  720

  P(n, r)   =  n! / (n - r)!

Десять человек и три разные медали дают семьсот двадцать способов, и одно правило умножения уже доводит до ответа: десять вариантов на золото, девять оставшихся на серебро, восемь на бронзу. Это упорядоченная выборка, записывается как P от n и r, а формула — убывающее произведение, обрывающееся после r множителей, то есть n факториал, делённый на n минус r факториал. Число велико только потому, что порядок считается информацией.

/* unordered choice: same 10 people, 3 identical seats */

  C(n, r)   =  P(n, r) / r!

  C(10, 3)  =  720 / (3 * 2 * 1)
            =  720 / 6
            =  120

Теперь уберём порядок. Те же три человека на пьедестале в другом порядке — не другое событие, если медали одинаковые, а одна группа. Каждая группа из трёх была посчитана три факториал раз, по разу на каждый порядок, поэтому деление на три факториал исправляет ровно этот пересчёт. Вот и вся причина, по которой делитель равен r факториал, а не какой-то другой поправке: это число порядков, которые вы только что решили не различать. C от 10 и 3 равно 120, в шесть раз меньше упорядоченного ответа, и правило на память такое: сочетания — это перестановки с поделённым порядком.

Принцип Дирихле — первый аргумент подсчёта, дающий гарантированный ответ, а не вероятный. Если n предметов разложены по m ящикам и n больше m, то в каком-то ящике лежит хотя бы два. Это всё, что он говорит, это очевидно — и тем не менее это один из самых полезных инструментов анализа алгоритмов, потому что он даёт уверенность из одного только подсчёта. Настоящее применение: у хеш-таблицы возможных ключей больше, чем корзин, поэтому коллизии — не признак плохой хеш-функции, а математическая неизбежность. Хорошая хеш-функция распределяет их равномерно, а не устраняет. Любое рассуждение вида «коллизий не будет, потому что хеш хороший» неверно ещё до начала.

Принцип Дирихле объясняет и то, почему вопрос «сколько нужно людей, чтобы у двоих совпал день рождения» — не тот вопрос, на который все отвечают первым. Люди сравнивают число людей с числом дней и говорят «сто восемьдесят». Но ящики здесь — не люди против дней, а пары людей против дней, а число пар растёт квадратично, тогда как число людей — линейно. При двадцати трёх людях пар уже двести пятьдесят три, и вероятность хотя бы одного совпадения около половины. Это та же схема, что и в аргументе про коллизии выше, и именно поэтому случайный идентификатор на шестьдесят четыре бита нормален, а на шестнадцать бит — это производственная авария.

birthday problem, 365 days

  two people differ:  364 / 365

  23 people:

  C(23, 2)  =  23 * 22 / 2  =  253 pairs

  (364 / 365)^253  =  0.4995
  1 - 0.4995       =  0.5005

  70 people:  1 - (364 / 365)^2415  >  0.999

Читайте числа дня рождения как предупреждение об интуиции, а не как фокус. Шестьдесят человек дают тысячу семьсот семьдесят пар, и вероятность совпадения переваливает за девяносто девять процентов. В этой арифметике нет ничего тонкого; удивление целиком происходит оттого, что мы оцениваем парные события как независимые, а они не независимы. Практическая версия для инженера: пространство коллизий квадратично по числу объектов, поэтому граница дня рождения всегда намного ниже наивной.

/* brute force, 10^9 steps per second */

n = 1    2!        =  2
n = 10   10!       =  3.6 * 10^6
n = 13   13!       =  6.2 * 10^9    6 seconds
n = 15   15!       =  1.3 * 10^12   22 minutes
n = 18   18!       =  6.4 * 10^15   74 days
n = 20   20!       =  2.4 * 10^18   77 years
n = 25   25!       =  1.6 * 10^25   5 * 10^8 years

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