-
Юбилейный DevConfX пройдет 21-22 июня в Москве. Как всегда — Вы решаете, кто попадет в программу секции Backend — голосуйте за интересные доклады
che
Guest
Я что-то упустил?
SelenIT
IT-лунатик :)
Один элемент мы по-любому выбираем, так что события как раз взаимоисключающие и сумма вероятностей равна 1 (условие нормировки). Следовательно, чтобы указанные при элементах вероятности соблюдались в точности, нужно каким-либо образом следить за соблюдением условия нормировки. Без этого смысл этих коэффициентов - то, что вероятность выбора будет распределена между элементами в такой пропорции. С такой поправкой алгоритм Крома работает.
che
Guest
Я же по русски разговариваю?
Имеем десять элементов, вероятность каждого 0.1, в сумме дают единицу.
Генерим случайное число (0-1 или 0-10, как удобнее) и сравниваем так, как предложил Кром. Расскажите мне, какое число будет выбрано, и как сравнивать если в массиве имеется хотя бы две одинаковых вероятности? если даже одинаковых нет, выдаваться будет не с той вероятностью что заказывалась
А теперь ту же ситуацию прогоняем через мой вариант.
После первого этапа имеем массив 0.1 0.2 0.3 0.4 ...1
Генерим число и находим ячейку массива, с наибольшим значением которое меньше либо равно сгенеренному, и отдаем число этой ячейке соответствующее.
Если это расчертить на бумажке в виде координатной линии то все встанет на свои места. И на бумаге и в голове.
P.S. То есть с наименьшим значением которое больше либо равно сгенеренному.
Имеем десять элементов, вероятность каждого 0.1, в сумме дают единицу.
Генерим случайное число (0-1 или 0-10, как удобнее) и сравниваем так, как предложил Кром. Расскажите мне, какое число будет выбрано, и как сравнивать если в массиве имеется хотя бы две одинаковых вероятности? если даже одинаковых нет, выдаваться будет не с той вероятностью что заказывалась
А теперь ту же ситуацию прогоняем через мой вариант.
После первого этапа имеем массив 0.1 0.2 0.3 0.4 ...1
Генерим число и находим ячейку массива, с наибольшим значением которое меньше либо равно сгенеренному, и отдаем число этой ячейке соответствующее.
Если это расчертить на бумажке в виде координатной линии то все встанет на свои места. И на бумаге и в голове.
P.S. То есть с наименьшим значением которое больше либо равно сгенеренному.
SelenIT
IT-лунатик :)
Сортировка по-моему лишняя - расположить интервалы на координатной линии можно и без нее.
Например, так:
1) находим сумму коэффициентов вероятности
2) генерируем случ. число от 0 до этой суммы. Пока все как и в исходном варианте.
3) пробегаем циклом по исходному массиву, для каждого элемента:
- прибавляем его коэффициент к сумме коэффициентов предыдущих;
- как только сумма стала больше случайного числа - заканчиваем цикл и выбираем этот элемент.
Суть та же, просто чуть меньше действий.
Например, так:
1) находим сумму коэффициентов вероятности
2) генерируем случ. число от 0 до этой суммы. Пока все как и в исходном варианте.
3) пробегаем циклом по исходному массиву, для каждого элемента:
- прибавляем его коэффициент к сумме коэффициентов предыдущих;
- как только сумма стала больше случайного числа - заканчиваем цикл и выбираем этот элемент.
Суть та же, просто чуть меньше действий.
che
Guest
Можно и так. Сортировка позволит на больших массивах делать поиск половинками, но здесь, я так понимаю не тот случай. Однако сумму с предыдущими элементами лучше вычислить сразу и навсегда, а не каждый раз на каждую генерацию 
Эээ... Опять туплю, после сложения они и так будут упорядочены по возрастанию.
Эээ... Опять туплю, после сложения они и так будут упорядочены по возрастанию.
che
Guest
А нет никакой перестройки. Надо просто массив один раз привести к интервалам и хранить в таком виде.
che
Guest
Выделить под это дело скрипт и место под кнопку в админке
В общем дело вкуса.
В общем дело вкуса.
Tsatur
Guest
Ну, и на чем остановились?
che
Guest
Последние 8(восемь) постов, включая этот.
Дополнительно массив заводить не надо!
Дополнительно массив заводить не надо!
valerchik
Guest
Ну так блин так и не вкурил, чё делать-то 
SelenIT
IT-лунатик :)
Два уточнения-дополнения к моему с che вчерашнему спору:
1) Довольно часто требуется выбирать несколько элементов без повторов, т.е. уже вероятность для уже выбранного искусственно обнуляется, а для остальных соответственно возрастает и перенормируется. В таком случае вариант с хранением массива интервалов впрок явно не проходит.
2) Если все-таки сортировать элементы для ускорения выборки, то не по возрастанию, а по убыванию вероятности - чтобы более вероятные элементы чаще выбирались уже на первых шагах.
1) Довольно часто требуется выбирать несколько элементов без повторов, т.е. уже вероятность для уже выбранного искусственно обнуляется, а для остальных соответственно возрастает и перенормируется. В таком случае вариант с хранением массива интервалов впрок явно не проходит.
2) Если все-таки сортировать элементы для ускорения выборки, то не по возрастанию, а по убыванию вероятности - чтобы более вероятные элементы чаще выбирались уже на первых шагах.
SiMM
Новичок
Развели тут дебаты из-за алгоритма в три строки...
Для тех, кто не понял Крома - читать сюда
Для тех, кто не понял Крома - читать сюда
PHP:
function random($ver,$rnd = false){
if ($rnd === false) $rnd = mt_rand(0,1e10)/1e10;
foreach ($ver as $k=>$v)
if ( ($rnd -= $v) <=0) return $k;
trigger_error('Сумма всех вероятностей недопустима', E_USER_WARNING);
return false;
}
echo random(array(1=>0.1,
2=>0.3,
3=>0.5,
));che
Guest
Не разумеет. То что сумма вероятностей равна единице говорит только о том что вероятности заданы правильно. Но сравниывать надо не с ними а с границами интервалов на координатной прямой которые эти вероятности займут на единичном отрезке независимо в каком порядке ты их расположишь. Именно для этого нужно предварительное суммирование. Твой код работать не будет, для 0.5 он будет выдавать не каждый второй раз как ожидалось бы а два раза из десяти (5-3)/10
Да, устроили дебаты. Потому что даже эти три строчки далеко не все могут правильно написать. пальчиком тычить не будем
SelenIT
Ни в коем разе. Ты не полностью понял алгоритм. Прокрути его в голове для генерации двух чисел, и ты поймешь что обнулять не надо.
Иэээх...
PHP:
function random ($ver, $rnd=false) {
($rnd===false) && $rnd=mt_rand(0, 10) ;
$c=0;
$res=0;
foreach ($ver as $k => $v) ($c+=$v*10)>= $rnd && $c-$v*10<$rnd && $res = $k;
$c==10 || trigger_error('Сумма всех вероятностей недопустима', E_USER_WARNING);
return $c==10 ? $res : false ;
}Убрал флаг - не нужен, все равно в диапазон только один раз попадет.
SelenIT
IT-лунатик :)
che
Прокручиваю. Пусть дан массив из 3-х элементов, вероятности 0.8, 0.15, 0.05. Надо выбрать 2 неповторяющихся.
Преобразуем в интервалы: [0 .. 0.8), [0.8 .. 0,95), [0.95 .. 1].
Допустим, первым выбран первый элемент массива, больше его выбирать нельзя. Разве те же интервалы применимы для выбора следующего элемента (второго или третьего)? Если да, то как?
Конечно, это немного отходит от первоначального вопроса темы, но раз уж начали поиски идеального алгоритма...
Наверное, в самом деле не понял. Даже стало интересно разобраться...
Прокручиваю. Пусть дан массив из 3-х элементов, вероятности 0.8, 0.15, 0.05. Надо выбрать 2 неповторяющихся.
Преобразуем в интервалы: [0 .. 0.8), [0.8 .. 0,95), [0.95 .. 1].
Допустим, первым выбран первый элемент массива, больше его выбирать нельзя. Разве те же интервалы применимы для выбора следующего элемента (второго или третьего)? Если да, то как?
Конечно, это немного отходит от первоначального вопроса темы, но раз уж начали поиски идеального алгоритма...
SiMM
Новичок
che, между прочим, если вы внимательно присмотритесь к моему алгоритму, то как раз таки и увидите, что сравнение происходит с границами интервалов
Конечно же, можно было бы переделать массив (0.1, 0.3, 0.5) в (0.1, 0.4, 0.9), только смысла в этом нет, поскольку из полученного случайного числа можно просто вычитать последовательно 0.1, 0.3, 0.5 и при получении результата, меньше нуля, делать соответствующие выводы.
И для вероятности 0.5 в моём коде всё работает не хуже, чем в твоём (в этом можешь убедиться, передав функции "нормальный" массив и сделав порядка 10000 опытов) - единственная ошибка, которую я допустил - забыл о том, что 1e10 - уже далеко не целое число, поэтому после его замены на 1e9 всё работает
Ключ с индексом 0 как раз показывает число "промахов", полученных благодаря тому, что у автора топика в исходной задаче сумма всех вероятностей неравна 1.
PS: в моём случае интервалы выглядит чуть иначе, чем у SilenITа - [0; 0.1], (0.1; 0.4], (0.4;0.9] + "довесок" (0.9; 1] - но положение строгого неравенства непринципиально.
-~{}~ 05.11.04 20:20:
Конечно же, можно было бы переделать массив (0.1, 0.3, 0.5) в (0.1, 0.4, 0.9), только смысла в этом нет, поскольку из полученного случайного числа можно просто вычитать последовательно 0.1, 0.3, 0.5 и при получении результата, меньше нуля, делать соответствующие выводы.
И для вероятности 0.5 в моём коде всё работает не хуже, чем в твоём (в этом можешь убедиться, передав функции "нормальный" массив и сделав порядка 10000 опытов) - единственная ошибка, которую я допустил - забыл о том, что 1e10 - уже далеко не целое число, поэтому после его замены на 1e9 всё работает
PHP:
function random($ver,$rnd = false){
if ($rnd === false) $rnd = mt_rand(0,1e9)/1e9; // согласен, облажался ;)
foreach ($ver as $k=>$v)
if ( ($rnd -= $v) <=0) return $k;
trigger_error('Сумма всех вероятностей недопустима', E_USER_WARNING);
return false;
}
$c=array();
for ($i=10000;$i--;)
@$c[random(array(1 => 0.1, 2 => 0.3, 3 => 0.5))]++;
ksort($c);
print_r($c);PS: в моём случае интервалы выглядит чуть иначе, чем у SilenITа - [0; 0.1], (0.1; 0.4], (0.4;0.9] + "довесок" (0.9; 1] - но положение строгого неравенства непринципиально.
-~{}~ 05.11.04 20:20:
Это заблуждение.
SelenIT
IT-лунатик :)
SiMM, прошу прощения, что продолжаю мусолить вопрос.
Кажется, все забыли, с чего начинался топик...
По поводу выбора случайных неповторяющися значений - это ограничивающее условие из другой задачи (притом нередко возникающей на практике - по крайней мере мне приходилось ее решать ).
Кажется, все забыли, с чего начинался топик...
Из определения вероятности и постановки задачи можно сделать вывод, что условие нормировки выполняется и недостающие до единицы 10% распределены между этими "и т.д." Если это не так, то это просто никакие не вероятности, а некие коэффициенты, пропорциональные им. Настоящие вероятности получатся, если поделить эти коэффициенты на их сумму. Ни о каких "промахах" имхо речь не идет - элемент должен быть выбран в любом случае.
По поводу выбора случайных неповторяющися значений - это ограничивающее условие из другой задачи (притом нередко возникающей на практике - по крайней мере мне приходилось ее решать
).SiMM
Новичок
Хорошо, скажу иначе - мне было лень додумывать это и т.д. за автора вопроса (фантазия у меня небогатая
) - такой вариант устраивает? Если есть желание, ты вполне можешь додумать это и т.д. самостоятельно - работоспособность кода от этого не пострадает (если сумма всех вероятностей равна 1 - он будет работать, а сообщение о том, что сумма вероятностей недопустима - лишь примочка к функции ).
Одна задача - один топик. Хочешь решать другую - открывай другой топик. А подобное твоему условие нужно разве что при размешивании карт колоды (если не ошибаюсь - это уже условные вероятности) - в теории событие с любой вероятностью может происходить хоть 10 раз подряд - другое дело, что вероятность такого повтора крайне низка, и возникновение подобной ситуации - проблема генератора псевдослучайных чисел или имеющихся условий.