Вычисление вероятности по относительным вероятностям

Cyrill

Новичок
У меня есть список, допустим это список пользователей. Нужно выбрать случайным образом 1 пользователя из этого списка учитывая то что каждый пользователь имеет относительную вероятность от 0 до 1.

Подскажите, как реализовать алгоритм!

p.s.: С Новым Годом, коллеги!
 

fixxxer

К.О.
Партнер клуба
Давай не от 0 до 1, а int от 0 до 100 например (хватит?).

Тогда делаешь массив, в котором каждый id пользователя повторяется заданное число раз, после чего берешь случайный элемент.

Хотя про "относительно" непонятно, относительно чего?
 

Cyrill

Новичок
Давай не от 0 до 1, а int от 0 до 100 например (хватит?).

Тогда делаешь массив, в котором каждый id пользователя повторяется заданное число раз, после чего берешь случайный элемент.

Хотя про "относительно" непонятно, относительно чего?
я тоже так подумал. сделать прямую на которой вероятность выбора пользователя от 0 до 100 отразить длинной его отрезка на этой прямой и потом случайно ткнуть на ней, в чей отрезок попал, тот и выбран))) по сути ваш ответ то же самое, только более приближено к математике. спасибо! с наступающим!
 

dimagolov

Новичок
IMHO идея в том, чтобы 1-й юзер (элемент) появлялся в 5% показов, 2-й в 7%, 3-й в 15%, 4-й в 10% и т.п. Ну или для простоты юзать не % (сумма которых должна быть 100%) а веса - 5, 7, 15, 10....

Итого, задача сводится к суммированию весов, генерации случайного числа от 1 до суммы и потом последовательным отниманием в цикле весов, пока остаток положительный. Как он стал отрицательным, так получили искомый элемент.
 

baev

‹°°¬•
Команда форума
Нужно выбрать случайным образом 1 пользователя из этого списка учитывая то что каждый пользователь имеет относительную вероятность от 0 до 1.
Это — не «случайным образом». А то, что Вы назвали «относительной вероятностью», называется простым термином «вес».
Вопросы типа «показа банеров с частотой пропорциональной их весам» на форуме поднимались неоднократно. Это давно уже не «теория программирования».

Тему переношу.
 

Cyrill

Новичок
PHP:
/**
 * weighted_random_simple()
 * Pick a random item based on weights.
 *
 * @param array $values Array of elements to choose from 
 * @param array $weights An array of weights. Weight must be a positive number.
 * @return mixed Selected element.
 */
function weighted_random_simple($values, $weights){ 
    $count = count($values); 
    $i = 0; 
    $n = 0; 
    $num = mt_rand(0, array_sum($weights)); 
    while($i < $count){
        $n += $weights[$i]; 
        if($n >= $num){
            break; 
        }
        $i++; 
    } 
    return $values[$i]; 
}
 

dimagolov

Новичок
Cyrill, если ты еще не понял, то это с точностью до знака реализация того алгоритма,что я изложил в своем посте :)
 
Сверху