Как выбрать элемент массива в зависимости от рейтинга?

Question

[KarambyG]

Дамы и господа, помогите решить одну проблему.
Предположим у меня есть массив с данными. Циферки - это их вес, в процентах.:

иван => 60
максим => 20
вова => 20

И возникла задача выбрать случайный элемент в зависимости от её веса. Например шанс, что будет выбран элемент "иван" больше, чем другие. Поскольку он имеет больше вес.
Подскажите как быть?..

Answer 1

[Сергей Соколов]

Второй вариант – то, что надо. Остаётся получить случайное от 0 до 4 (с равномерным распределением) и взять соотв. имя. У Ивана шансов как раз 3/5.

Upd.

function getRandomWinner($ppl)
{
  $choice = rand(0, array_sum(array_values($ppl)) - 1);

  $sum = 0;
  foreach($ppl as $name => $rank) {
    $sum += $rank;
    if ($choice < $sum) return $name;
  }
}

$winnerName = getRandomWinner([
  'Иван' => 60,
  'Максим' => 20,
  'Вова' => 20,
]);

Comments

[KarambyG]

извиняюь, немного не так дал условие)
у меня в % значения.

иван => 60
максим => 20
вова => 20

Как быть в данном случае?)

[Сергей Соколов]

KarambyG, принцип тот же: 20 вов, 20 максимов и 60 иванов. Случайное от 0 до суммы всех - 1 = 99

[Сергей Соколов]

KarambyG, собственно достаточно сложить все, взять случайное [0..99], и посмотреть, куда оно попало.
0..59 - Иван,
60..79 - Максим
80..99 - Вова

[KarambyG]

Сергей Соколов, а как это реализовать правильно? тоесть сгенерировать через цикл массив на 100 элементов? в них создать 60 элементов иванов, и по 20 вов и максимов?
или есть более лучший способ?)

[Сергей Соколов]

KarambyG,

function getRandomWinner($ppl)
{
  $choice = rand(0, array_sum(array_values($ppl)) - 1);

  $sum = 0;
  foreach($ppl as $name => $rank) {
    $sum += $rank;
    if ($choice < $sum) return $name;
  }
}

$winnerName = getRandomWiner([
  'Иван' => 60,
  'Максим' => 20,
  'Вова' => 20,
]);

[KarambyG]

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

Как написать такой кодик для динамического массива я хз :(

[Сергей Соколов]

KarambyG, обновил коммент

[KarambyG]

Сергей Соколов, ооо спасибо! меня как раз за минуту до твоего комментария осенило, и я придумал такое же решение сам) Только ты постоянно прибавлял в цикле, а я наоборот, брал сумму, и каждый раз отнимал :)
Спасибо, навёл меня на мысль :)

[Fedor Vlasenko]

Сергей Соколов поясните магию строчек

$sum += $rank;
    if ($choice < $sum) return $name;

[Сергей Соколов]

Fedor Vlasenko, смысл алгоритма – бросать случайное на отрезок, длина которого общая сумма всех шансов участников. Так получится, что на более длинный отрезок шансов попасть больше, чем на короткий. Так и получаем разные вероятности соответственно заданным шансам.

Тут $sum – это "running sum", бегущая сумма. Идём по списку и на каждой строчке добавляем к сумме значение в ячейке.

Например, всего 2 имени. Алиса с "весом" 3 и Боб с 1. Т.е. у Алисы шансов в 3 раза больше.
Сумма (длина отрезка) 4.
Берём случайное от 0 до 3 (длина 4)

0  1  2  3
А  А  А  Б

Получилось, например, $choice = 3.
Идём по списку. Алиса. $sum была 0 стала 3. $choice < $sum ? нет. Идём дальше.
Боб. $sum была 3 стала 4. $choice наконец < $sum – значит, попали в нужный интервал - Боб.

[KarambyG]

Сергей Соколов, Кстати, а если у меня 1000 строк? или 10 тыщ? тоже по такой же методике работать? Или есть более упрошённый способ с точки зрения нагрузки?

[Сергей Соколов]

KarambyG, нагрузка незаметная даже для телефона. Если не выбирать «победителя» снова и снова для каждого пикселя экрана 60 раз в секунду )