Привет, Хабр! В этой статье я приведу простой алгоритм, позволяющий группе из N человек секретно сгенерировать каждому из участников группы номер другого участника — одариваемого — для обмена подарками на Новый год в мероприятии Тайный Санта (Secret Santa).
Прежде всего, что такое Тайный Санта? Статья в Википедии рассказывает это лучше меня, я лишь кратко скажу, что это церемония, пришедшая к нам с Запада, в которой группа людей сговаривается подарить на Новый год друг другу подарки таким образом, что каждый из участников дарит и получает по одному подарку, при этом каждому не известен его даритель, но известен одариваемый (отсюда "тайный Санта"). Стоимость подарков обычно оговаривается заранее, чтобы все подарки были примерно равноценны. При желании можно условиться, что после того, как обмен подарками совершится, дарители раскроются.
Свой "Тайный Санта" есть и на Хабрахабре под названием "Клуб Анонимных Дедов Морозов".
К сожалению, для организации Тайного Санты просто сгенерировать список пар даритель-одариваемый недостаточно. Дарение должно происходить анонимно, и каждый участник должен знать только номер одариваемого и ни битом информации больше о других участниках, поэтому, например, нельзя просто поручить одному из участников сгенерировать список и сообщить каждому оставшемуся участнику его одариваемого — тот, кто сгенерировал список, будет знать всё обо всех, в том числе и своего дарителя.
Как правило, участники выходят из положения, прибегая к помощи "третьей стороны" — незаинтересованного человека, не участвующего в церемонии, которого просят сгенерировать номера одариваемых и тайно сообщить каждому участнику единственный номер. Такой "третьей стороной" может быть не только человек, но и специализированный сайт, к числу которых относится и уже упомянутый "Клуб АДМ" Хабрахабра.
Если же поставить условие децентрализованности (отсутствия "третьей стороны"),
то "Тайный Санта" превращается в интересную с точки зрения криптографии задачу, достаточно хорошо изученную и неоднократно решённую: вот пример математической модели Тайного Санты, а вот конкретный алгоритм решения, где участники для обеспечения скрытия данных используют асимметричное шифрование.
В данной статье я опишу ещё один такой алгоритм. Его небольшое преимущество перед прочими методами из области хардкорной криптографии в том, что он очень прост в исполнении: всё, что надо делать участникам, — это записывать наборы натуральных чисел, а также вычёркивать из них отдельные элементы и вписывать новые.
Как и остальные децентрализованные алгоритмы для Тайного Санты, этот алгоритм не требует "третьей стороны" — участникам достаточно только общаться между собой. Всё, что требуется каждому участнику, — это дважды получить от участника с предыдущим номером набор натуральных чисел, изменить его определённым образом и передать следующему. После того, как обмен наборами завершится, каждый участник определённым образом формирует из имеющихся у него наборов единственное натуральное число — номер одариваемого.
Сразу скажу, у такого подхода не очень много преимуществ по сравнению с тем, чтобы просто привлечь "третью сторону", но пара плюсов всё-таки есть:
- Это просто весело — поиграть на НГ в "Тайного Санту" с криптографией. Хорошо подойдёт компании гиков.
- Не требуется искать человека со стороны, организовывать его общение с каждым из участников.
- Не требуется регистрироваться ни на каком сайте, нужны только сами участники и минимум технических средств общения обычным текстом. При физической встрече участников не нужно ничего, кроме ручки и бумаги. Для общения на расстоянии подойдёт что угодно — электронная почта, SMS, IRC...
Описание алгоритма
Для начала, небольшое соглашение о том, как представлять конкретный набор, сопоставляющий дарителей и одариваемых, с математической точки зрения.
Назначение одариваемых в Тайном Санте — не что иное, как назначение каждому из участников группы из N человек номера от 1 до N, означающего номер одариваемого (если считать, что все участники пронумерованы от 1 до N). При этом:
- Никому не должен достаться свой собственный номер (тк нельзя дарить себе самому);
- Не должно быть номеров, никому не доставшихся (тк все должны быть одарены);
- Номер каждого участника достаётся ровно одному дарителю (тк каждый должен получить ровно 1 подарок).
- Двум участникам может выпасть дарить подарки друг другу — в принципе это совершенно нормально, но иногда участники могут условиться перебрасывать жребий в этом случае.
- На номера могут накладываться другие дополнительные ограничения в зависимости от ситуации (например, если в "Санте" участвуют несколько семей, они могут условиться перебрасывать жребий, если кому-то из участников выпало делать подарок члену своей семьи).
Отсюда видно, что любой список пар даритель-одариваемый для Secret Santa можно представить в виде последовательности из N чисел (на i-ом месте записывается номер того, кому дарит подарок i-ый участник), представляющей собой перестановку порядка N без неподвижных точек.
Первый этап алгоритма
Итак, каждому участнику назначается номер от 1 до N, например в алфавитном порядке имён. Эта информация является открытой и сообщается всем участникам.
Затем первый участник случайным образом создаёт большой набор (нужно не менее 2N) натуральных чисел так, что никакие 2 из них не совпадают. Этот набор изначально не сообщается никому. Первый участник записывает эти числа для удобства в порядке возрастания, выбирает себе любое одно из них случайным образом, удаляет выбранное число из набора и передаёт оставшийся набор второму участнику. В итоге у первого участника оказываются записанными 2 вещи: стартовый набор чисел и выбранное им число.
Приведём пример с 5 участниками.
Первый участник генерирует начальный набор: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003
Выбрано: 783
Передаётся второму участнику: 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Второй участник точно так же выбирает себе из набора произвольное число, удаляет его из набора и передаёт оставшийся набор следующему участнику. Так же поступают 3-ий, 4-ый и 5-ый участник. Пятый, последний, участник выбирает себе число, но никому ничего пока не передаёт.
Продолжим пример:
Второй участник получает (повторим ещё раз): 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Второй участник выбирает: 3
Третий участник получает: 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Третий участник выбирает: 94
Четвёртый участник получает: 46, 50, 89, 95, 101, 500, 5003, 5765, 7003
Четвёртый участник выбирает: 5765
Пятый участник получает: 46, 50, 89, 95, 101, 500, 5003, 7003
Пятый участник выбирает: 101
Остаток набора: 46, 50, 89, 95, 500, 5003, 7003
На этом первый этап алгоритма окончен. Комментарий: в итоге у каждого из участников имеется число, не известное всем остальным (точнее, каждому участнику известен большой набор чисел, про который он знает, что последующие участники выбирали своё число из него — но это не даёт никакой информации, позволяющей точно узнать чужие числа). Если мы теперь найдём способ как-то сообщить весь набор выбранных чисел каждому из участников, то задача назначения дарителей будет решена: каждому участнику достаточно взять за конечный результат порядковый номер выбранного им числа в этом наборе выбранных номеров.
Предположим, что мы уже нашли способ сообщить каждому набор выбранных номеров (вообще мы это сделаем на 2-ом этапе алгоритма) и участники узнали номера своих одариваемых. Проблема в том, что одному или более участникам могут выпасть их собственные номера, что делает весь итоговый результат некорректным. Это большой минус алгоритма, так как вероятность попасть в эту ситуацию довольно высока, хотя она и падает с ростом N. Выходов как минимум 2:
Участник, получивший свой собственный номер, запрашивает у всех перебрасывание жребия с начала. Эту процедуру нужно повторять, пока все не подтвердят, что им достался корректный номер.
- Участник, получивший свой собственный номер, запрашивает у всех применение к итоговым результатам случайной перестановки без неподвижных точек. Эта перестановка генерируется открыто и сообщается всем участникам. Каждый участник должен применить эту перестановку к номеру своего одариваемого. Эту процедуру нужно повторять, пока все не подтвердят, что им достался корректный номер. Этот способ подходит только при физической встрече, так как при удалённом общении невозможно гарантировать случайность перестановки (тот, кому задано сгенерировать перестановку, к примеру, может беспрепятственно сгенерировать перестановку, переводящую его номер одариваемого в любой другой номер одариваемого по его желанию).
В примере с 5 участниками вот как будут выглядеть выбранные номера:
1-ый участник выбрал (повторим ещё раз): 783
2-ой участник выбрал (повторим ещё раз): 3
3-ий участник выбрал (повторим ещё раз): 94
4-ый участник выбрал (повторим ещё раз): 5765
5-ый участник выбрал (повторим ещё раз): 101
Список выбранных номеров в порядке возрастания (повторюсь — предположим, что мы знаем, как секретно сообщить его всем участникам): 3 94 101 783 5765
Итого, номера одариваемых:
1-ый участник: выбрал 783, набор 3 94 101 783 5765 — номер одариваемого 4
2-ой участник: выбрал 3, набор 3 94 101 783 5765 — номер одариваемого 1
3-ий участник: выбрал 94, набор 3 94 101 783 5765 — номер одариваемого 2
4-ый участник: выбрал 5765, набор 3 94 101 783 5765 — номер одариваемого 5
5-ый участник: выбрал 101, набор 3 94 101 783 5765 — номер одариваемого 3
Переброса не требуется.
Второй этап алгоритма
Итак, как же сообщить всем набор "выделенных" номеров? Это задача второго этапа. Узнать этот набор может первый участник, если последний участник сообщит ему оставшийся в конце набор (в примере это 46, 50, 89, 95, 500, 5003, 7003). Первому участнику тогда достаточно исключить этот набор из стартового, и результат исключения будет искомым набором выбранных участниками чисел. Заметим, что первый участник при таком действии всё ещё не знает никакой информации, позволяющей ему раскрыть номера, доставшиеся остальным участникам.
К сожалению, просто взять и сообщить вычисленный набор дальше по цепочке нельзя — хотя бы потому, что предпоследний участник по этой информации мгновенно вычислит номер, выбранный последним участником, а значит и узнает его одариваемого.
Решение у этой проблемы следующее. Как уже сказано, последний участник передаёт первому самый последний оставшийся набор. У первого участника оказываются следующие данные:
Стартовый набор: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003
Выбрано число: 783
Последний остаток набора: 46, 50, 89, 95, 500, 5003, 7003
Первый участник вычисляет, как уже сказано выше, набор выбранных всеми участниками чисел: 3, 94, 101, 783, 5765 и узнаёт выпавший ему номер одариваемого — 4.
Теперь, начиная с этого момента, каждый участник, начиная с первого, будет сообщать следущему участнику набор из N чисел. Каждый, получивший такой набор, должен считать его набором выбранных всеми участниками номеров и соответственно вычислить номер своего одариваемого. Но на каждом шаге передаваться дальше будет не оригинальный набор выбранных номеров, а изменённый, но дающий тот же результат вычисления номера одариваемого, что и оригинальный. При этом изменённый набор исключит всякую возможность узнать выбранные другими числа.
Для составления такого изменённого набора участник должен взять полученный им от предыдущего участника набор (в случае первого участника — набор, вычисленный как сказано выше) и подменить в нём своё число (выбранное на 1ом этапе) на любое другое число из доставшегося ему на 1-ом этапе набора, со следующими ограничениями:
- Заменённое число не должно входить в только что полученный от предыдущего участника набор;
- Заменённое число должно иметь тот же порядковый номер в изменённом наборе, что и заменяемое число в оригинальном наборе.
В примере первый участник подменяет в наборе 3, 94, 101, 783, 5765 выбранное им число — 783. Числа, которые ему разрешено подставить вместо 783, — это 500 и 5003. Предположим, он выбрал подмену 783 на 5003 и передаёт второму участнику набор 3, 94, 101, 5003, 5765.
Остальные участники делают то же самое. Доведём пример до конца.
Второй участник:
Набор на 1ом этапе — 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Выбранное число — 3
Набор на 2ом этапе — 3, 94, 101, 5003, 5765
Можно подставить вместо 3 — 46, 50, 89
Выбираем подставить 50, передаём дальше набор 50, 94, 101, 5003, 5765
Третий участник:
Набор на 1ом этапе — 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Выбранное число — 94
Набор на 2ом этапе — 50, 94, 101, 5003, 5765
Можно подставить вместо 94 — 89, 95
Выбираем подставить 89, передаём дальше набор 50, 89, 101, 5003, 5765
Четвёртый участник:
Набор на 1ом этапе — 46, 50, 89, 95, 101, 500, 5003, 5765, 7003
Выбранное число — 5765
Набор на 2ом этапе — 50, 89, 101, 5003, 5765
Можно подставить вместо 5765 — 7003
Выбираем подставить 7003 (альтернатив особо нет), передаём дальше набор 50, 89, 101, 5003, 7003
Пятый участник:
Набор на 1ом этапе — 46, 50, 89, 95, 101, 500, 5003, 7003
Выбранное число — 101
Набор на 2ом этапе — 50, 89, 101, 5003, 7003
Обмен наборами закончен, участники могут заняться вычислением номера одариваемого.
Можно удостовериться, что никто из участников при таком подходе не может узнать ничего о чужих номерах.
Всё, алгоритм завершён. Навскидку я вижу в нём ещё 2 недостатка, помимо упомянутых выше частых перебросов из-за шанса выпадения участнику своего собственного номера:
Случайность выбора участником числа из набора никак не гарантируется. Никто не мешает первому участнику, например, выбрать последнее число в наборе и тем самым практически обеспечить себе номер одариваемого, равный N. Эта проблема устраняется, если, как уже сказано, участники договорятся в самом конце алгоритма дополнительно применить к результатам известную всем случайную перестановку без неподвижных точек, но её случайность тоже нужно как-то гарантировать.
- Алгоритм не умеет создавать никакие дополнительные ограничения на номера одариваемых (например, запрет любым 2 участникам или определённым 2 участникам взаимно делать подарок друг другу).
Всем спасибо, кто дочитал до конца, и с наступающим Новым годом :) Печеньку тому, кто найдёт ещё проблемы в алгоритме или решит существующие!
Комментарии (40)
Daniro_San
26.12.2016 05:22-1церемония, пришедшая к нам с Запада
Запад с большой буквы?mwambanatanga
26.12.2016 06:19+2Да, конечно. Это имя собственное — цивилизация, в которую входят страны Западной Европы (снова имя собственное), Северной Америки и т.д… Если писать с маленькой буквы, то получится буквально: пешее путешествие оттуда, где заходит солнце.
Dark_Snake
26.12.2016 09:41Как то сложно. Когда делал подобное — отталкивался от четности\нечетности.
Если участников четное число — то для каждого последовательно берется 1 случайный номер из N (число участников) отличный от уже использованных номеров, и номера его самого.
Если нечетное — то выбираются любые 3 участника, для них реализуется схема A->B->C->A. Оставшееся реализуется по четному принципу.
pewpew
26.12.2016 09:59Как-то не менее сложно. Без привязки к чётности делал несколько лет назад…
кусок кода$user_ids = array(); foreach ($active_users as $i=>$u) { $user_ids[] = $u['id']; } shuffle($user_ids); foreach ($active_users as $i=>$u) { $random_user_id = 0; while (($random_user_id == 0) && (count($user_ids) > 0)) { if ($user_ids[0] != $u['id']) { $random_user_id = array_shift($user_ids); $query = "UPDATE `adm`.`users` SET `victim`={$random_user_id} WHERE `id`=".$u['id']; $res = mysql_query($query); } else { shuffle($user_ids); } } }Dark_Snake
26.12.2016 13:59о том и речь, главное что бы не выпал, поэтому я так и реализовывал. Так-то можно проще 1->2-3>… ->1
TimsTims
26.12.2016 10:00> К сожалению, для организации Тайного Санты просто сгенерировать список пар даритель-одариваемый недостаточно.
Вы слишком всё усложняете. Всё это кодится в течение 30 минут на любом ЯП через пару циклов. Да, нужно вводить исключения — чтобы самому себе нельзя было дарить, и чтобы нельзя, чтобы в процессе «выдёргиваний» людей из цикла, не остался один человек без подарка.
> начальный набор: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003
Зачем 7003, 5765? Можно ведь просто 1,2,3,4,5. Да и то, цифры пусть остаются в алгоритме, а людям сообщать просто имена одариваемых.
Как накодил я:
1-й главный цикл, который повторяется, пока все условия не выполнены (на самом деле можно было бы рекурсивную функцию использовать, но не суть).
2) цикл for, с перебором всех участников (20 человек), присываиванием случайного санты из набора одариваемых.
3) Проверка, что все участники имеют и дарителя и одариваемого. иначе повторить с п.1
4) Запись результато в БД.
5) Совсем маленькая прога на Android, которая рассылает смс-ки всем участникам. Да, смс-ки платные (у йоты почти бесплатные). Да, если я очень захочу, то смогу посмотреть, кто и кому дарил, но это уже становится не интересно.
Но в итоге — всё кодится очень просто и быстро. Да, возможно реализация на несколько процессорных тактов уступает возможным оптимизациям, но суть была не взорвать себе мозг, а решить задачку случайного распределения. И третьей «не заинтересованной» стороной мы посчитали компьютер, который всё это сделает.Steed
26.12.2016 12:23+3Не нужно никаких проверок — достаточно случайно перемешать линейный список участников, далее первый дарит второму, второй — третьему, ..., последний — первому. Ситуации дарения самому себе (при N>1) и отсутствия дарителя исключены.
Cheater
26.12.2016 13:04> Вы слишком всё усложняете. Всё это кодится в течение 30 минут на любом ЯП через пару циклов.
Как и многие другие комменты к этой статье, ваш комментарий и все вопросы в нём касаются задачи с третьей стороной. Статья рассматривает ситуацию, когда третья сторона запрещена. Сгенерировать пары даритель-одариваемый не проблема, это то же самое, что сгенерировать перестановку порядка N без неподвижных точек, и в статье при описании алгоритма я молчаливо считал, что это операция, выполняемая «за бесплатно».
Основная проблема — организовать скрытый обмен данными, если участие третьей стороны запрещено. Это автоматически делает любые данные, сгенерированные у кого-то кроме себя самого (неважно, скриптом или ручкой на бумаге), скомпрометированными.
> Можно ведь просто 1,2,3,4,5.
Нельзя, потому что второй участник, получивший оставшиеся 4 числа от первого участника, мгновенно узнает, какое число тот выбрал.TimsTims
26.12.2016 13:49-2ситуацию, когда третья сторона запрещена
Почему 3я сторона запрещена? Мы ведь в тайного Санту играем, а не в "передай подарок тайному агенту ЦРУ без привлечения ФСБ"
Cheater
26.12.2016 16:09Традициями Тайного Санты третья сторона ест-но не запрещена, каждый волен выбирать механизм назначения дарителей по своему желанию. Но введение искусственного запрета на третью сторону создаёт математически содержательную задачу, а задача с третьей стороной особо содержательной не является (за исключением разве что написания нехитрого скрипта на Perl или на чём ещё для перемешивания N элементов)
YaMishar
26.12.2016 12:23-1По-моему сам процесс перемешивания можно реализовать на экселе очень просто.
Берём список участников (может уже быть закодирован), добавляем колонкой формулу rand(), сортируем по ней.
В результате имеем случайным образом отсортированный список.
В нём каждый дарит подарок следующему.
Ну а последний — первому.
Из плюсов — никаких циклов, никаких взаимных подарков.
mogilka
26.12.2016 12:23-1Я на своём сайте делала так:
/** * Перемешивание случайным образом массива чисел с учётом того, * чтобы значения исходного и полученного массивов по идентичным индексам не дублировались * @param array $list исходный массив чисел * @return array перемешанный массив */ public static function randomArray($list) { $target = array(); $used = array(); foreach ($list as $k=>$v) { $tmp = $list; //удаляем первое значение пары unset($tmp[$k]); //удаляем ранее использованные вторые значения пар foreach ($used as $u) if (($i = array_search($u, $tmp)) !== false) unset($tmp[$i]); $tk = array_rand($tmp); $t = $tmp[$tk]; $target[$k] = $t; $used[] = $t; } return $target; }
Участников обычно не бывает больше 30, срабатывает быстро, с учётом последующей записи в базу. Да хоть 1000 участников. Самый трудоёмкий процесс — рассылку Тайным Сантам почтовых сообщений с именем адресата — выполняю отдельно после завершения транзакции. Организаторы ничего не знают о парах участников. После распределения пар каждый знает только своего получателя. А чтобы не дарить кота в мешке, Тайные Санты ещё получают уведомления о том, что хотят получить в подарок адресаты
ov7a
26.12.2016 12:26+1Разве в этой схеме нельзя искусственно повысить шанс выбора первого участника, если всегда брать минимальное число?
ov7a
26.12.2016 12:35С подменой неясно, исключена ли ситуация, когда тупо не на что заменить число?
При перевыборах, кажется, можно скомпрометировать свой номер, если было несколько неудачных попыток.Cheater
26.12.2016 12:47> С подменой неясно, исключена ли ситуация, когда тупо не на что заменить число?
Нет, не исключена, к сожалению. Самый простой вариант — опять запрашивать переброс в таком случае. Разрешить просто не заменять число нельзя, это приводит к раскрытию не заменённого числа (док-во лениво писать).
Ещё можно брать очень большой набор, тк чем больше его размер, тем меньше вероятность такого исхода.
> При перевыборах, кажется, можно скомпрометировать свой номер, если было несколько неудачных попыток.
Верно. Похоже, надо каждый раз переназначать номера участников.ov7a
26.12.2016 13:03Насколько я понимаю, размер набора никак не улучшит ситуацию, если все участники намеренно будут хотеть ломать схему, выбирая минимальные числа из доступных.
Если надо переназначать номера участников, то получается как в bogosort — авось повезет, авось нет. В худшем случае будете до посинения перевыбирать номера и это быстро всем надоест.
Cheater
26.12.2016 12:40Верно, я упоминаю эту проблему в статье и это фактически самая большая проблема алгоритма:
> Случайность выбора участником числа из набора никак не гарантируется.
Единственный способ, который мне приходит в голову, — это подвергнуть финальный результат публично известному случайному перемешиванию, но как его сгенерировать без третьей стороны, я пока не придумал.ov7a
26.12.2016 13:00Можно сгенерировать номер случайной перестановки по алгоритму Диффи-Хэллмана?
Cheater
26.12.2016 15:29Да, DH должен сработать (+только что прочитал https://en.wikipedia.org/wiki/Commitment_scheme — есть ряд других способов), но простота реализации уже вижу что исчезает окончательно.
my_fess
26.12.2016 12:48Проблема в том, что одному или более участникам могут выпасть их собственные номера, что делает весь итоговый результат некорректным. Это большой минус алгоритма, так как вероятность попасть в эту ситуацию довольно высока, хотя она и падает с ростом N.
Если я не ошибаюсь, вероятность не особо падает, она примерно равна (1 — 1/e) вне зависимости от N (Кроме N=1 и N=2). То есть эта вероятность почти всегда 63%.
ru.wikipedia.org/wiki/Беспорядок_(перестановка)
kafeman
26.12.2016 14:21Какие-то очень сложные алгоритмы предлагаются выше для централизованного АДМ. У нас это сделано так:
Берется список всех участников, копируется, генерируется некое случайное натуральное число 0 < R < N, где N — количество участников, после чего второй список (копия) «прокручивается» на R позиций.
Готово! Теперь у нас есть два списка длиной N — первый содержит ключи («Деды Морозы»), второй содержит значения («Внуки» или «Внучки»). Работает для любого N > 2, и не важно, четное это число, или не четное. Все происходит за долю секунды.my_fess
26.12.2016 15:48Тогда человек точно знает что тот кому он дарит подарок — не дарит ему, а это уже не так интересно. Да и в случае N=3 каждый точно знает кто у кого тайный Санта. Получается не очень тайно.
Jeksonic
28.12.2016 00:59В случае N=3 и так все знают кто кому секретный Сатна, поскольку если 1 дарит 2, а 2 дарит 1, то 3 остается без подарка, что исключается условиями задачи.
Cheater
26.12.2016 15:49Это в принципе работает, но у такого подхода есть небольшой минус — если стартовый список не рандомизирован (например это список по алфавиту), ваш алгоритм генерирует довольно небольшое подмножество (состоящее из всего N вариантов) множества всех корректных перестановок (в котором, грубо, 0.37*N! элементов — см. коммент https://habrahabr.ru/post/318412/#comment_9983218). Если же вы его рандомизируете вначале, то затраты на рандомизацию значительно больше затрат на сдвиг.
kafeman
26.12.2016 15:58Список отсортирован по первичному ключу, который инкриминируется при регистрации нового участника.
Не вижу ничего плохого в ограниченном количестве вариантов сортировки. На самом деле, даже если мы возьмем R за константу, то все-равно сохранится анонимность.
Shark
27.12.2016 19:28Когда-то сам писал подобную штуку. В итоге остановился на модифицированном алгоритме Фишера–Йейтса: модификация заключалась в том что как только номер который мы записываем оказывается на своей же позиции, тут же начинаем заново (сюда же добавлялись условия вроде Боб не дарит Алисе, потому что они пара, а значит будут дарить подарки друг другу в любом случае).
Ради спортивного интереса я старался сделать математически «честного» санту, а такой способ дает равномерное распределение без всяких уклонов. Примерно 1/3 всех случайных сортировок удовлетворяют условиям тайного санты, потому, хоть в теории он может зациклиться бесконечно, на практике такой метод работает достаточно быстро.
Killy
28.12.2016 14:57Sergo96
03.01.2017 00:35Если представить, что неких 3 участника выбрали 3 подряд идущих номера, то на втором этапе, первый из них не сможет ничем заменить свой номер.
Например, есть 3 участника и изначальный набор из 6-и чисел:
2 5 11 21 23 54
Допустим, участники выбрали номера: 21, 23, 11 соответственно.
Когда отсортированный набор (11, 21, 23) придет первому участнику на втором этапе, он не будет иметь чем заменить свое число не нарушив порядок.
foxin
этот алгоритм сильно уступает другим, где участникам не нужно ничего делать.
Cheater
Под другими имеются в виду алгоритмы с третьей стороной? В ситуации без третьей стороны во всех известных мне алгоритмах участники должны выполнять довольно много действий, без этого не организовать скрытый обмен данными.
Ingref
В чём проблема написать на листочках номера одариваемых, положить в мешок, перемешать, а потом каждый случайным образом вытащит номер? Тогда никто, кроме дарителя, не будет знать номер. И третья сторона тоже.
Ekkeir
Есть вероятность вытащить свой номер. Или остаться последним со единственным собственным номером в мешке.
Ingref
В случае вытаскивания своего номера просто номер кладётся обратно, перемешивается и снова тащится случайный номер. В случае, если я остался последний со своим номером — все кладут вытащенные листочки обратно и розыгрыш повторяется заново. Вероятность того, что такая ситуация произойдёт дважды, крайне мала, поэтому в большинстве случаев хватит одного, в крайнем случае двух розыгрышей.
Shark
Ingref
OK, тогда люди могут брать листочки не сразу друг за другом, а, допустим, в течение дня с утра до вечера. Тогда никто не будет следить (если специально не подсчитывать), кто уже вытянул листочек, а кто нет. Тогда и я не буду знать, сколько человек уже вытащило листочки до меня и сколько еще осталось.
Ingref
Либо еще вариант — все собираются вместе в одно время, завязывают глаза, один человек с мешком по очереди подходит к каждому и даёт вытянуть листочек, потом в конце вытягивает сам. После этого все развязывают повязки и смотрят, не вытянул ли кто-нибудь самого себя. Если вытянул — розыгрыш повторяется. Если нет — никто ничего не знает, кроме номера одариваемого.