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

[Cyrill]

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

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

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

 

[HraKK]

Ты сам то понял что написал?

 

[fixxxer]

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

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

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

 

[Ragazzo]

Я думаю тут нужны лекции по тер.вер.

 

[Cyrill]

Ты сам то понял что написал?

не. а о чем я ?

 

[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.

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

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

 

[HraKK]

Элементарная задача

 

[Cyrill]

/**
 * 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]; 
}

 

[Cyrill]

источник к пояснения тут
http://w-shadow.com/blog/2008/12/10/fast-weighted-random-choice-in-php/

 

[dimagolov]

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

 

[Cyrill]

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

да понятно все. просто привел код и статью на тему, для будущих покалений