Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 41
всё, что надо делать участникам, — это записывать наборы натуральных чисел, а также вычёркивать из них отдельные элементы и вписывать новые.
этот алгоритм сильно уступает другим, где участникам не нужно ничего делать.
Под другими имеются в виду алгоритмы с третьей стороной? В ситуации без третьей стороны во всех известных мне алгоритмах участники должны выполнять довольно много действий, без этого не организовать скрытый обмен данными.
В чём проблема написать на листочках номера одариваемых, положить в мешок, перемешать, а потом каждый случайным образом вытащит номер? Тогда никто, кроме дарителя, не будет знать номер. И третья сторона тоже.
Есть вероятность вытащить свой номер. Или остаться последним со единственным собственным номером в мешке.
В случае вытаскивания своего номера просто номер кладётся обратно, перемешивается и снова тащится случайный номер. В случае, если я остался последний со своим номером — все кладут вытащенные листочки обратно и розыгрыш повторяется заново. Вероятность того, что такая ситуация произойдёт дважды, крайне мала, поэтому в большинстве случаев хватит одного, в крайнем случае двух розыгрышей.
В случае вытаскивания своего номера просто номер кладётся обратно, перемешивается и снова тащится случайный номер.Не все так просто. Если я вытащил свой номер — я знаю что его не вытащил никто до меня. А если я предпоследний, то я точно знаю кто мой санта.
OK, тогда люди могут брать листочки не сразу друг за другом, а, допустим, в течение дня с утра до вечера. Тогда никто не будет следить (если специально не подсчитывать), кто уже вытянул листочек, а кто нет. Тогда и я не буду знать, сколько человек уже вытащило листочки до меня и сколько еще осталось.
Либо еще вариант — все собираются вместе в одно время, завязывают глаза, один человек с мешком по очереди подходит к каждому и даёт вытянуть листочек, потом в конце вытягивает сам. После этого все развязывают повязки и смотрят, не вытянул ли кто-нибудь самого себя. Если вытянул — розыгрыш повторяется. Если нет — никто ничего не знает, кроме номера одариваемого.
церемония, пришедшая к нам с Запада
Запад с большой буквы?
Как то сложно. Когда делал подобное — отталкивался от четности\нечетности.
Если участников четное число — то для каждого последовательно берется 1 случайный номер из N (число участников) отличный от уже использованных номеров, и номера его самого.
Если нечетное — то выбираются любые 3 участника, для них реализуется схема A->B->C->A. Оставшееся реализуется по четному принципу.
Если участников четное число — то для каждого последовательно берется 1 случайный номер из N (число участников) отличный от уже использованных номеров, и номера его самого.
Если нечетное — то выбираются любые 3 участника, для них реализуется схема A->B->C->A. Оставшееся реализуется по четному принципу.
Как-то не менее сложно. Без привязки к чётности делал несколько лет назад…
Код уже морально устарел, но всё ещё работает. Алгоритм, думаю вполне понятен. Просто смешиваем всех со всеми, главное чтобы юзеру не выпал он сам.
кусок кода
$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);
}
}
}
Код уже морально устарел, но всё ещё работает. Алгоритм, думаю вполне понятен. Просто смешиваем всех со всеми, главное чтобы юзеру не выпал он сам.
> К сожалению, для организации Тайного Санты просто сгенерировать список пар даритель-одариваемый недостаточно.
Вы слишком всё усложняете. Всё это кодится в течение 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, которая рассылает смс-ки всем участникам. Да, смс-ки платные (у йоты почти бесплатные). Да, если я очень захочу, то смогу посмотреть, кто и кому дарил, но это уже становится не интересно.
Но в итоге — всё кодится очень просто и быстро. Да, возможно реализация на несколько процессорных тактов уступает возможным оптимизациям, но суть была не взорвать себе мозг, а решить задачку случайного распределения. И третьей «не заинтересованной» стороной мы посчитали компьютер, который всё это сделает.
Вы слишком всё усложняете. Всё это кодится в течение 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, которая рассылает смс-ки всем участникам. Да, смс-ки платные (у йоты почти бесплатные). Да, если я очень захочу, то смогу посмотреть, кто и кому дарил, но это уже становится не интересно.
Но в итоге — всё кодится очень просто и быстро. Да, возможно реализация на несколько процессорных тактов уступает возможным оптимизациям, но суть была не взорвать себе мозг, а решить задачку случайного распределения. И третьей «не заинтересованной» стороной мы посчитали компьютер, который всё это сделает.
Не нужно никаких проверок — достаточно случайно перемешать линейный список участников, далее первый дарит второму, второй — третьему, ..., последний — первому. Ситуации дарения самому себе (при N>1) и отсутствия дарителя исключены.
> Вы слишком всё усложняете. Всё это кодится в течение 30 минут на любом ЯП через пару циклов.
Как и многие другие комменты к этой статье, ваш комментарий и все вопросы в нём касаются задачи с третьей стороной. Статья рассматривает ситуацию, когда третья сторона запрещена. Сгенерировать пары даритель-одариваемый не проблема, это то же самое, что сгенерировать перестановку порядка N без неподвижных точек, и в статье при описании алгоритма я молчаливо считал, что это операция, выполняемая «за бесплатно».
Основная проблема — организовать скрытый обмен данными, если участие третьей стороны запрещено. Это автоматически делает любые данные, сгенерированные у кого-то кроме себя самого (неважно, скриптом или ручкой на бумаге), скомпрометированными.
> Можно ведь просто 1,2,3,4,5.
Нельзя, потому что второй участник, получивший оставшиеся 4 числа от первого участника, мгновенно узнает, какое число тот выбрал.
Как и многие другие комменты к этой статье, ваш комментарий и все вопросы в нём касаются задачи с третьей стороной. Статья рассматривает ситуацию, когда третья сторона запрещена. Сгенерировать пары даритель-одариваемый не проблема, это то же самое, что сгенерировать перестановку порядка N без неподвижных точек, и в статье при описании алгоритма я молчаливо считал, что это операция, выполняемая «за бесплатно».
Основная проблема — организовать скрытый обмен данными, если участие третьей стороны запрещено. Это автоматически делает любые данные, сгенерированные у кого-то кроме себя самого (неважно, скриптом или ручкой на бумаге), скомпрометированными.
> Можно ведь просто 1,2,3,4,5.
Нельзя, потому что второй участник, получивший оставшиеся 4 числа от первого участника, мгновенно узнает, какое число тот выбрал.
ситуацию, когда третья сторона запрещена
Почему 3я сторона запрещена? Мы ведь в тайного Санту играем, а не в "передай подарок тайному агенту ЦРУ без привлечения ФСБ"
Традициями Тайного Санты третья сторона ест-но не запрещена, каждый волен выбирать механизм назначения дарителей по своему желанию. Но введение искусственного запрета на третью сторону создаёт математически содержательную задачу, а задача с третьей стороной особо содержательной не является (за исключением разве что написания нехитрого скрипта на Perl или на чём ещё для перемешивания N элементов)
По-моему сам процесс перемешивания можно реализовать на экселе очень просто.
Берём список участников (может уже быть закодирован), добавляем колонкой формулу rand(), сортируем по ней.
В результате имеем случайным образом отсортированный список.
В нём каждый дарит подарок следующему.
Ну а последний — первому.
Из плюсов — никаких циклов, никаких взаимных подарков.
Берём список участников (может уже быть закодирован), добавляем колонкой формулу rand(), сортируем по ней.
В результате имеем случайным образом отсортированный список.
В нём каждый дарит подарок следующему.
Ну а последний — первому.
Из плюсов — никаких циклов, никаких взаимных подарков.
Я на своём сайте делала так:
Участников обычно не бывает больше 30, срабатывает быстро, с учётом последующей записи в базу. Да хоть 1000 участников. Самый трудоёмкий процесс — рассылку Тайным Сантам почтовых сообщений с именем адресата — выполняю отдельно после завершения транзакции. Организаторы ничего не знают о парах участников. После распределения пар каждый знает только своего получателя. А чтобы не дарить кота в мешке, Тайные Санты ещё получают уведомления о том, что хотят получить в подарок адресаты
/**
* Перемешивание случайным образом массива чисел с учётом того,
* чтобы значения исходного и полученного массивов по идентичным индексам не дублировались
* @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 участников. Самый трудоёмкий процесс — рассылку Тайным Сантам почтовых сообщений с именем адресата — выполняю отдельно после завершения транзакции. Организаторы ничего не знают о парах участников. После распределения пар каждый знает только своего получателя. А чтобы не дарить кота в мешке, Тайные Санты ещё получают уведомления о том, что хотят получить в подарок адресаты
Разве в этой схеме нельзя искусственно повысить шанс выбора первого участника, если всегда брать минимальное число?
С подменой неясно, исключена ли ситуация, когда тупо не на что заменить число?
При перевыборах, кажется, можно скомпрометировать свой номер, если было несколько неудачных попыток.
При перевыборах, кажется, можно скомпрометировать свой номер, если было несколько неудачных попыток.
> С подменой неясно, исключена ли ситуация, когда тупо не на что заменить число?
Нет, не исключена, к сожалению. Самый простой вариант — опять запрашивать переброс в таком случае. Разрешить просто не заменять число нельзя, это приводит к раскрытию не заменённого числа (док-во лениво писать).
Ещё можно брать очень большой набор, тк чем больше его размер, тем меньше вероятность такого исхода.
> При перевыборах, кажется, можно скомпрометировать свой номер, если было несколько неудачных попыток.
Верно. Похоже, надо каждый раз переназначать номера участников.
Нет, не исключена, к сожалению. Самый простой вариант — опять запрашивать переброс в таком случае. Разрешить просто не заменять число нельзя, это приводит к раскрытию не заменённого числа (док-во лениво писать).
Ещё можно брать очень большой набор, тк чем больше его размер, тем меньше вероятность такого исхода.
> При перевыборах, кажется, можно скомпрометировать свой номер, если было несколько неудачных попыток.
Верно. Похоже, надо каждый раз переназначать номера участников.
Насколько я понимаю, размер набора никак не улучшит ситуацию, если все участники намеренно будут хотеть ломать схему, выбирая минимальные числа из доступных.
Если надо переназначать номера участников, то получается как в bogosort — авось повезет, авось нет. В худшем случае будете до посинения перевыбирать номера и это быстро всем надоест.
Если надо переназначать номера участников, то получается как в bogosort — авось повезет, авось нет. В худшем случае будете до посинения перевыбирать номера и это быстро всем надоест.
Верно, я упоминаю эту проблему в статье и это фактически самая большая проблема алгоритма:
> Случайность выбора участником числа из набора никак не гарантируется.
Единственный способ, который мне приходит в голову, — это подвергнуть финальный результат публично известному случайному перемешиванию, но как его сгенерировать без третьей стороны, я пока не придумал.
> Случайность выбора участником числа из набора никак не гарантируется.
Единственный способ, который мне приходит в голову, — это подвергнуть финальный результат публично известному случайному перемешиванию, но как его сгенерировать без третьей стороны, я пока не придумал.
Проблема в том, что одному или более участникам могут выпасть их собственные номера, что делает весь итоговый результат некорректным. Это большой минус алгоритма, так как вероятность попасть в эту ситуацию довольно высока, хотя она и падает с ростом N.
Если я не ошибаюсь, вероятность не особо падает, она примерно равна (1 — 1/e) вне зависимости от N (Кроме N=1 и N=2). То есть эта вероятность почти всегда 63%.
ru.wikipedia.org/wiki/Беспорядок_(перестановка)
Все статьи на этом сайте https://habrahabr.ru/ полезные и грамотные
Какие-то очень сложные алгоритмы предлагаются выше для централизованного АДМ. У нас это сделано так:
Берется список всех участников, копируется, генерируется некое случайное натуральное число 0 < R < N, где N — количество участников, после чего второй список (копия) «прокручивается» на R позиций.
Готово! Теперь у нас есть два списка длиной N — первый содержит ключи («Деды Морозы»), второй содержит значения («Внуки» или «Внучки»). Работает для любого N > 2, и не важно, четное это число, или не четное. Все происходит за долю секунды.
Берется список всех участников, копируется, генерируется некое случайное натуральное число 0 < R < N, где N — количество участников, после чего второй список (копия) «прокручивается» на R позиций.
Готово! Теперь у нас есть два списка длиной N — первый содержит ключи («Деды Морозы»), второй содержит значения («Внуки» или «Внучки»). Работает для любого N > 2, и не важно, четное это число, или не четное. Все происходит за долю секунды.
Точнее, для любого N > 1.
Тогда человек точно знает что тот кому он дарит подарок — не дарит ему, а это уже не так интересно. Да и в случае N=3 каждый точно знает кто у кого тайный Санта. Получается не очень тайно.
Это в принципе работает, но у такого подхода есть небольшой минус — если стартовый список не рандомизирован (например это список по алфавиту), ваш алгоритм генерирует довольно небольшое подмножество (состоящее из всего N вариантов) множества всех корректных перестановок (в котором, грубо, 0.37*N! элементов — см. коммент https://habrahabr.ru/post/318412/#comment_9983218). Если же вы его рандомизируете вначале, то затраты на рандомизацию значительно больше затрат на сдвиг.
Когда-то сам писал подобную штуку. В итоге остановился на модифицированном алгоритме Фишера–Йейтса: модификация заключалась в том что как только номер который мы записываем оказывается на своей же позиции, тут же начинаем заново (сюда же добавлялись условия вроде Боб не дарит Алисе, потому что они пара, а значит будут дарить подарки друг другу в любом случае).
Ради спортивного интереса я старался сделать математически «честного» санту, а такой способ дает равномерное распределение без всяких уклонов. Примерно 1/3 всех случайных сортировок удовлетворяют условиям тайного санты, потому, хоть в теории он может зациклиться бесконечно, на практике такой метод работает достаточно быстро.
Ради спортивного интереса я старался сделать математически «честного» санту, а такой способ дает равномерное распределение без всяких уклонов. Примерно 1/3 всех случайных сортировок удовлетворяют условиям тайного санты, потому, хоть в теории он может зациклиться бесконечно, на практике такой метод работает достаточно быстро.
Можно юзать сервис mysanta.ru
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм для секретного назначения дарителей в Secret Santa