Жребьевка в интернете

Кол-во интернет-турниров растет и вопрос может стать актуальным. Требования к жребьевке такие - все ее участники должны находится в равных условиях, жребьевка должна быть проверяемой. В основном, может быть два варианта: прожеребить группу из 2n участников между собой или две группы по n участников друг с другом.
Первый вариант. Участники упорядочиваются от 1 до 2n (можно по рейтингу). На первом шаге потребуется сгенерить случайное число от 1 до 2n-1 (пара 1-му игроку.) На втором шаге оставишиеся участники снова упорядочиваются от 1 до 2n-2 и генерится сл. число от 1 до 2n-3 (пара 1-му из оставшихся после 1-шага игроков). И т.д. пока не останется два игрока, которые играют между собой.
Второй вариант.
Участники в обеих группах упорядочиваются от 1 до n (можно по рейтингу). На первом шаге потребуется сгенерить случайное число от 1 до n (пара 1-му игроку из старшей группы). На втором шаге оставшиеся участники в обеих группах снова упорядочиваются от 1 до n-1 и генерится сл. число от 1 до n-1 (пара 1-му из оставшихся после 1-шага игроков в старшей группе). И т.д. пока не останется по одному игроку в каждой группе, которые играют между собой.
Генерация случ. числа в интернете решается просто.

Простой способ сгенрить псевдослуч. число это взять кол-во просмотров посещаемого канала на ютьбе.
Статистика берется на сайте socialblade. Чтобы получить из числа просмотров случ. число от 1 до n можно взять остаток от деления этого числа на n и добавить 1. Из одного числа просмотров можно получить несколько псевдосл. чисел от 1 до n1, от 1 до n2..., если n1,n2... взаимно простые (не содержат общих делителей).

Пример. Предположим, что нам надо свести 5 человек из верхней группы (ВГ) с 5 из нижней (НГ). Нам надо сгенерировать 4 сл. числа от 1 до 5, от 1 до 4, от 1 до 3 и от 1 до2. Для этого достаточно взять всего два числа просмотров, так как 2,3,5 взаимно-простые.

Самые посещаемые на сегодня каналы на ютьбе
[socialblade.com]
и [socialblade.com]
К счастью, смотреть их необязательно, достаточно взять статистику по Subscribers на вчера (т.к. она идет онлайн): 7,170 (из него генерим 3 числа от 1 до 2,3,5) и 15,360 (из него генерим 1 число от 1 до 4).

Итак,
Для 1 игрока из верхней группы
7170 mod 5 +1 =1, значит 1ВГ играет с 1НГ.
Для 2 игрока из верхней группы
15,360 mod 4+1 =1, значит 2ВГ играет с 2НГ (1НГ уже играет с 1 ВГ).
Для 3 игрока из верхней группы
7170 mod 3+1 =1, значит 3ВГ играет с 3НГ.
Для 4 игрока из верхней группы
7170 mod 2+1 =1, значит 4ВГ играет с 4НГ.

Ну и последняя пара 5ВГ - 5НГ.

Quote
peripatetik
Простой способ сгенрить псевдослуч. число это взять кол-во просмотров посещаемого канала на ютьбе.
Статистика берется на сайте socialblade.

простой способ генерации случайного числа - это генерация случайного числа с предварительной инициализацией генератора текущим временем.

Например на php, например, будет так:
<?php
function make_seed()
{
list($usec, $sec) = explode(' ', microtime());
return (float) $sec + ((float) $usec * 100000);
}
srand(make_seed());
$randval = rand();
?>

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

дубль

Конечно. Поэтому и нужно внешнее псевдослучайное число, про которое заранее известно, откуда оно берется.

Кстати, добавка к алгоритму жоебьевки. Еще нужно определить цвет. Если есть n партий, то их нужно пронумеровать, потом сгенерировать сл. число от 0 до n-1, потом взять его в бинарной форме и считать, что 1 это когда игрок старший по рейтингу в паре играет черными.

Quote
peripatetik
псевдослучайное число, про которое заранее известно, откуда оно берется

А берется оно из источника, на который несложно повлиять в необходимом ключе, выполнив предварительные расчеты.

Ок. Использование генератора случайных чисел для генерации случайных чисел считаем не правильным. Инициализацию генератора таймером для получения заранее не известной последовательности так же считаем не верной.
Тогда другой вариант, который позволит получить заранее предсказуемую и всегда одинаковую последовательность случайных чисел, на которую будет достаточно сложно повлиять.
Каждому турниру присваиваем уникальный идентификатор. Например это может быть GUID (он же 128 битное число, которое в момент генерации статистически уникально), запись вида ГГГГГММДД*количество участников. Полученным числом, либо его частью (например младшие 32 бита GUID) инициализируем генератор псевдослучайных чисел и генерируем. Генерируем игровые пары на весь турнир.

В результате получаем полную автоматизацию, невозможность подделать результат (в случае введения в начальное число неизвестной переменной, такой как количество участников), полная прозрачность и возможность проверить результаты.

>>А берется оно из источника, на который несложно повлиять в необходимом ключе, выполнив предварительные расчеты.
________________________________________
Очень сомневаюсь. Число порядка 10 тыс, +1 за 8 сек, время фиксации результата неизвестно. Но если входить в параноидальный режим, то можно брать данные eur-usd с finam.ru в заранее заданный момент времени. Но, давайте попробуем. Сделайте завтра на [socialblade.com]
число Subscribers/change кратным 5.

>> Полученным числом, либо его частью (например младшие 32 бита GUID) инициализируем генератор псевдослучайных чисел и генерируем
____________________________________
Где взять генератор, за которым могут наблюдать все участники?

[ladder.goportal.ru] — комментарии к партиям на русском языке



Редактировано 1 раз(а). Последний раз 19/11/2012 20:29 пользователем Shedal.