Как стать автором
Обновить

Комментарии 41

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

этот алгоритм сильно уступает другим, где участникам не нужно ничего делать.
Под другими имеются в виду алгоритмы с третьей стороной? В ситуации без третьей стороны во всех известных мне алгоритмах участники должны выполнять довольно много действий, без этого не организовать скрытый обмен данными.
В чём проблема написать на листочках номера одариваемых, положить в мешок, перемешать, а потом каждый случайным образом вытащит номер? Тогда никто, кроме дарителя, не будет знать номер. И третья сторона тоже.
Есть вероятность вытащить свой номер. Или остаться последним со единственным собственным номером в мешке.
В случае вытаскивания своего номера просто номер кладётся обратно, перемешивается и снова тащится случайный номер. В случае, если я остался последний со своим номером — все кладут вытащенные листочки обратно и розыгрыш повторяется заново. Вероятность того, что такая ситуация произойдёт дважды, крайне мала, поэтому в большинстве случаев хватит одного, в крайнем случае двух розыгрышей.
В случае вытаскивания своего номера просто номер кладётся обратно, перемешивается и снова тащится случайный номер.
Не все так просто. Если я вытащил свой номер — я знаю что его не вытащил никто до меня. А если я предпоследний, то я точно знаю кто мой санта.
OK, тогда люди могут брать листочки не сразу друг за другом, а, допустим, в течение дня с утра до вечера. Тогда никто не будет следить (если специально не подсчитывать), кто уже вытянул листочек, а кто нет. Тогда и я не буду знать, сколько человек уже вытащило листочки до меня и сколько еще осталось.
Либо еще вариант — все собираются вместе в одно время, завязывают глаза, один человек с мешком по очереди подходит к каждому и даёт вытянуть листочек, потом в конце вытягивает сам. После этого все развязывают повязки и смотрят, не вытянул ли кто-нибудь самого себя. Если вытянул — розыгрыш повторяется. Если нет — никто ничего не знает, кроме номера одариваемого.
церемония, пришедшая к нам с Запада

Запад с большой буквы?
НЛО прилетело и опубликовало эту надпись здесь
Как то сложно. Когда делал подобное — отталкивался от четности\нечетности.
Если участников четное число — то для каждого последовательно берется 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);
		}
	}
}

Код уже морально устарел, но всё ещё работает. Алгоритм, думаю вполне понятен. Просто смешиваем всех со всеми, главное чтобы юзеру не выпал он сам.
о том и речь, главное что бы не выпал, поэтому я так и реализовывал. Так-то можно проще 1->2-3>… ->1
> К сожалению, для организации Тайного Санты просто сгенерировать список пар даритель-одариваемый недостаточно.
Вы слишком всё усложняете. Всё это кодится в течение 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 числа от первого участника, мгновенно узнает, какое число тот выбрал.
ситуацию, когда третья сторона запрещена

Почему 3я сторона запрещена? Мы ведь в тайного Санту играем, а не в "передай подарок тайному агенту ЦРУ без привлечения ФСБ"

Традициями Тайного Санты третья сторона ест-но не запрещена, каждый волен выбирать механизм назначения дарителей по своему желанию. Но введение искусственного запрета на третью сторону создаёт математически содержательную задачу, а задача с третьей стороной особо содержательной не является (за исключением разве что написания нехитрого скрипта на Perl или на чём ещё для перемешивания N элементов)
По-моему сам процесс перемешивания можно реализовать на экселе очень просто.
Берём список участников (может уже быть закодирован), добавляем колонкой формулу rand(), сортируем по ней.
В результате имеем случайным образом отсортированный список.
В нём каждый дарит подарок следующему.
Ну а последний — первому.

Из плюсов — никаких циклов, никаких взаимных подарков.
Я на своём сайте делала так:

	/**
	 * Перемешивание случайным образом массива чисел с учётом того,
	 * чтобы значения исходного и полученного массивов по идентичным индексам не дублировались
	 * @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 — авось повезет, авось нет. В худшем случае будете до посинения перевыбирать номера и это быстро всем надоест.
Верно, я упоминаю эту проблему в статье и это фактически самая большая проблема алгоритма:

> Случайность выбора участником числа из набора никак не гарантируется.

Единственный способ, который мне приходит в голову, — это подвергнуть финальный результат публично известному случайному перемешиванию, но как его сгенерировать без третьей стороны, я пока не придумал.
Можно сгенерировать номер случайной перестановки по алгоритму Диффи-Хэллмана?
Да, DH должен сработать (+только что прочитал https://en.wikipedia.org/wiki/Commitment_scheme — есть ряд других способов), но простота реализации уже вижу что исчезает окончательно.
Проблема в том, что одному или более участникам могут выпасть их собственные номера, что делает весь итоговый результат некорректным. Это большой минус алгоритма, так как вероятность попасть в эту ситуацию довольно высока, хотя она и падает с ростом 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, и не важно, четное это число, или не четное. Все происходит за долю секунды.
Точнее, для любого N > 1.
Тогда человек точно знает что тот кому он дарит подарок — не дарит ему, а это уже не так интересно. Да и в случае N=3 каждый точно знает кто у кого тайный Санта. Получается не очень тайно.
У нас список участников закрытый.
В случае N=3 и так все знают кто кому секретный Сатна, поскольку если 1 дарит 2, а 2 дарит 1, то 3 остается без подарка, что исключается условиями задачи.
Это в принципе работает, но у такого подхода есть небольшой минус — если стартовый список не рандомизирован (например это список по алфавиту), ваш алгоритм генерирует довольно небольшое подмножество (состоящее из всего N вариантов) множества всех корректных перестановок (в котором, грубо, 0.37*N! элементов — см. коммент https://habrahabr.ru/post/318412/#comment_9983218). Если же вы его рандомизируете вначале, то затраты на рандомизацию значительно больше затрат на сдвиг.
Список отсортирован по первичному ключу, который инкриминируется при регистрации нового участника.

Не вижу ничего плохого в ограниченном количестве вариантов сортировки. На самом деле, даже если мы возьмем R за константу, то все-равно сохранится анонимность.
Когда-то сам писал подобную штуку. В итоге остановился на модифицированном алгоритме Фишера–Йейтса: модификация заключалась в том что как только номер который мы записываем оказывается на своей же позиции, тут же начинаем заново (сюда же добавлялись условия вроде Боб не дарит Алисе, потому что они пара, а значит будут дарить подарки друг другу в любом случае).

Ради спортивного интереса я старался сделать математически «честного» санту, а такой способ дает равномерное распределение без всяких уклонов. Примерно 1/3 всех случайных сортировок удовлетворяют условиям тайного санты, потому, хоть в теории он может зациклиться бесконечно, на практике такой метод работает достаточно быстро.
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории