Раздать имена в Тайном Санте — задача на пять строк: перемешал список, проверил, что никто не достался сам себе, готово. Я так и думал, пока не посчитал. При таком способе почти в четырёх играх из десяти найдутся двое, которые дарят друг другу, и это не баг реализации, а свойство случайных перестановок.

Я делаю сервис для Тайного Санты (My Santa), и жеребьёвка в нём — те самые пять строк, которые разрослись до ста тридцати. Ниже — почему разрослись, как устроены и какой перекос я нашёл в собственном коде, пока готовил цифры для этой статьи.

Три способа, которыми это делают обычно

Шляпа. Все по очереди тянут бумажку; вытянул себя — тянешь другую. Проблема в последнем: если к его очереди в шляпе осталась только его бумажка, тянуть нечего. Я смоделировал это честно, со случайным выбором на каждом шаге:

В отделе из восьми человек игру придётся перетягивать примерно каждый одиннадцатый раз. После второго круга все уже видели чужие бумажки.

Перемешать и проверить. Берём случайную перестановку; если у кого‑то выпал он сам — перемешиваем заново. Перестановок без неподвижных точек примерно 1/e от всех, так что в среднем нужно около 2,7 попытки (в прогоне вышло от 2,67 для четверых до 2,72 для больших игр). Это работает и это пишут чаще всего.

Но посмотрим, что получается на выходе. Перестановка распадается на циклы, и цикл длины два — это пара людей, которые дарят друг другу. Среднее число таких циклов в случайной перестановке равно 1/2, их количество распределено почти по Пуассону, и запрет неподвижных точек на это не влияет. Вероятность, что хотя бы один двойной цикл есть: 1 − e^(−1/2) ≈ 39,3%.

Прогон на 200 тысячах игр:

Начиная с шести человек от размера игры это не зависит: в компании из пятидесяти шанс тот же.

Чем взаимная пара плоха? Формально ничем, правила соблюдены. Но в момент вручения оба понимают всё сразу, а до раскрытия ещё неделя. У нас к тому же есть анонимный чат: каждый может писать своему подопечному и отвечать своему Санте. Во взаимной паре это два чата с одним и тем же человеком, и анонимность живёт до первой характерной фразы. То же с тройками: три человека, замкнутые друг на друга, быстро вычисляют, кто кому.

Таблица. Тот же второй способ, только организатор видит результат. Алгоритмически обсуждать нечего.

Один круг

Решение известное: строим не произвольную перестановку, а один цикл через всех. Аня дарит Боре, Боря Вере, и так до последнего, который дарит Ане. Замкнутых групп меньше всей компании не бывает по построению.

Получить такой цикл просто: перемешать список и считать, что каждый дарит следующему, а последний — первому.

rng.Shuffle(len(order), func(i, j int) { order[i], order[j] = order[j], order[i] })
for i, santa := range order {
    out[santa] = order[(i+1)%len(order)]
}

На этом можно было бы закончить, если бы не исключения.

«Муж не дарит жене»

В семье дарить «своему» неинтересно, в отделе неловко, когда начальник достаётся подчинённому. Организатор до жеребьёвки собирает группы людей, которые друг другу не дарят. Участники этих групп не видят.

Самое простое, что можно сделать с ограничениями, — выборка с отклонением: перемешали, проверили весь круг, не подошёл — перемешали снова.

func cycleFits[T comparable](order []T, allowed func(santa, giftee T) bool) bool {    for i, santa := range order {        if !allowed(santa, order[(i+1)%len(order)]) {            return false        }    }    return true}

Хорошее свойство сохраняется: подошедший порядок — это равновероятный круг среди разрешённых. Вопрос только в том, как часто он подходит. Для восьми человек это можно посчитать точно, перебрав все 5040 кругов:

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

Когда перемешиванием не получается

В первой версии я остановился на 64 попытках. Дальше включался запасной путь из двух шагов.

Шаг первый: найти хоть какое‑то распределение. Это паросочетание в двудольном графе: слева все в роли Сант, справа все в роли подопечных, ребро — «этому можно дарить тому». Алгоритм Куна, классика олимпиадного программирования, только списки рёбер и порядок обхода перемешаны, чтобы результат не был одним и тем же.

Паросочетание даёт перестановку, но не обязательно один круг. Обычно это несколько кругов.

Шаг второй: склеить круги. Берём двоих из разных кругов и меняем им подопечных. Если Аня дарила Боре в одном круге, а Глеб дарил Даше в другом, то после обмена Аня дарит Даше, Глеб — Боре, и два круга стали одним. Это общее свойство перестановок: умножение на транспозицию двух элементов из разных циклов сливает циклы. Обмен делаем, только если обе новые пары разрешены.

func joinCircles[T comparable](players []T, out map[T]T, allowed func(santa, giftee T) bool) {
    for {
        circle := circlesOf(players, out)
        a, b, ok := joinable(players, out, circle, allowed)
        if !ok {
            return
        }
        out[a], out[b] = out[b], out[a]
    }
}

Склеить удаётся не всегда, потому что одного круга может не существовать в принципе. Пример: два лагеря по трое, и дарить разрешено только внутри своего лагеря. Распределение есть, круга через всех нет, получится два круга по три человека.

Когда раздать нельзя вообще

Двенадцать человек, семеро из них — один отдел. Семерым нужны семь разных подопечных не из отдела, а таких людей пятеро. Это теорема Холла в бытовом виде: если какой‑то группе Сант на всех доступно меньше подопечных, чем их самих, распределения нет.

Паросочетание в этом случае не находится, и это точный ответ, а не «не повезло». Что делает сервис:

• организатор запускает жеребьёвку сам — отказ и подсказка. Если есть человек, которому не осталось вообще никого, называем его; это самый частый случай, и его видно простым проходом;

• жеребьёвка идёт по расписанию — не проводим её и оставляем игру открытой. Молча выбросить чьё‑то ограничение хуже, чем подождать организатора.

Проверка на честность, ради которой я сел писать

Для статьи хотелось написать фразу «распределение равномерное». Написать её, не проверив, было бы неловко, поэтому я проверил.

Для маленькой игры все разрешённые круги можно перечислить, а потом разыграть несколько миллионов жеребьёвок и посмотреть, как часто выпадает каждый. При равномерном выборе все круги выпадают одинаково часто с точностью до шума (при 4000 выпадений на круг шум — несколько процентов).

Я взял три набора ограничений без симметрии, чтобы перекос не мог спрятаться, и измерил оба пути по отдельности:

Числа — отношение к ровной доле. У перемешивания это шум. У запасного пути — нет: некоторые круги выпадают на четверть чаще положенного, некоторые на шестую часть реже. Алгоритм Куна и жадная склейка никому равномерности не обещали, и было бы странно, если бы она получилась сама.

Насколько это важно, зависит от того, как часто включается запасной путь. А включался он часто — там, где ограничения тесные:

То есть в семейной игре на двадцать человек больше половины жеребьёвок шли через путь с перекосом. На целой жеребьёвке это выглядело скромнее. Игра на девятерых: отдел из четырёх, пара, и начальник отдела не дарит ещё двоим. Разрешённых кругов 816 из 40 320, запасной путь включался в 27% игр, самый частый круг выпадал в 1,13 раза чаще ровной доли, самый редкий — в 0,93. Никто из игроков этого бы не заметил. Но фразу «распределение равномерное» писать было нельзя.

Починка в одну строку

Число 64 я когда‑то взял с потолка. Одна попытка для двенадцати игроков — доли микросекунды, так что экономить их незачем.

const (
    minShuffles = 64
    shuffleWork = 400_000
)

func shuffles(n int) int {
    return max(minShuffles, shuffleWork/n)
}

Теперь бюджет задан в работе, а не в попытках: около 400 тысяч шагов «игрок на попытку». Для игры на двенадцать человек это 33 тысячи перемешиваний вместо 64. Вероятность, что при доле 0,2% ни одно не подойдёт, — порядка e^(−70).

После правки та же игра на девятерых: самый редкий круг 0,95×, самый частый 1,04× — шум. Запасной путь остался для случаев, где одного круга нет вовсе.

Цена. Обычная жеребьёвка:

Худший случай — когда круга нет или раздать нельзя, и бюджет сгорает целиком: 2–3 мс. Для операции, которая выполняется один раз за игру, это ничто.

Чего здесь нет

Равномерности в запасном пути. Он по‑прежнему с перекосом, просто теперь до него почти не доходит. Честно выбрать случайное паросочетание равномерно — задача другого уровня сложности (подсчёт совершенных паросочетаний #P‑полон), и для игры в подарки я её решать не стал.

Криптостойкого генератора. Генератор — PCG из math/rand/v2, зерно берётся из глобального источника рантайма. Предсказать жеребьёвку, не зная зерна, нельзя, но PCG не криптографический. Если бы на кону стояло что‑то дороже свечки с запахом ёлки, я бы взял ChaCha8 с зерном из crypto/rand.

Защиты от организатора с доступом к базе. Пары лежат в таблице. Организатор игры их не видит, но тот, кто администрирует сервер, технически может. Это вопрос доверия к сервису, а не алгоритма.

Что я из этого вынес

Число, взятое с потолка, стоит хотя бы раз проверить измерением. У меня оно прожило в коде незамеченным, потому что тесты проверяли, что результат допустимый, а равномерность — только для игры без ограничений, где запасной путь не включается никогда. Тест на равномерность занял тридцать строк: перечислить круги, разыграть двести тысяч раз, сравнить доли.

И вопрос к тем, кто дочитал: есть ли дешёвый способ выбрать случайный гамильтонов цикл равномерно, когда доля подходящих совсем мала? Выборка с отклонением упирается в долю, цепи Маркова по перестановкам кажутся избыточными для задачи про подарки. Если знаете что‑то изящное — расскажите.