Как выводить случайное значение но с определённой вероятностью?

12
aleksey_php
На сайте с 17.03.2008
Offline
53
8817

Есть таблица городов:

Название | Вероятность
Москва | 80%
Питер | 50%
Воронеж | 20%
Новосибирск | 20%
Урюпинск | 10%
Тольятти | 30%
Усть-Кулом | 10%

Необходимо выводить на странице 3 любых города из этой таблицы, но с учётом их вероятности. Т.е. при 10 обновлениях страницы мы увидим Москву, Питер и Тольятти чаще других, т.к. их вероятность попасть в случайный список больше, чем у остальных. Почему список случайный? Потому что он каждый раз формируется заново и, например, Москва попадёт в него, грубо говоря, в 8 случаях из 10.

Если кто-нибудь сталкивался с подобным, то подскажите как решить данную задачу.

[Удален]
#1

Какая-то у вас вероятность неправильная. Правильнее будет, если сумма всех вариантов равна 100%.

Допустим так:

Москва | 50%

Питер | 25%

Воронеж | 10%

Новосибирск | 5%

Урюпинск | 5%

Тольятти | 3%

Усть-Кулом | 2%

Таким образом создаём массив из 100 элементов, где 50 элементов имеют индекс Москвы, 25 индекс Питера.... Далее просто выбираем случайное значение из этого массива.

HraKK
На сайте с 02.03.2009
Offline
128
#2

aleksey_php, если уж больше 100% получается то имеет смысл не писать проценты, а просто говорить что это вес.

Делается так - складываете вес, и генерируете рандомное число от 1 до суммы.

Потом смотрите в какой отрезок вошла полученное число, то и выводим.

HraKK добавил 27.05.2009 в 02:10

nikitian, опередили с ответом, пока я писал. Но в моем посте, немного больше про вес. Что и имел ввиду ТС, просто некорректно указав %.

я гарант (/ru/forum/493343) уже не оказываю данные услуги, извините.
aleksey_php
На сайте с 17.03.2008
Offline
53
#3

К сожалению, в моём случае речь всё-таки идёт именно о процентах, но проценты в таблице указываются не относительно других городов, а относительно двух состояний для одного города:

1. в списке

2. не в списке

Т.е. для города Москва есть 80% вероятность того, что он попадёт в список и его наличие в этом списке никак не влияет на возможность любого другого города попасть в этот список. Т.е. каждый город "сам за себя".

Пока писал этот пост родилось решение стоящего вопроса:

1) сортируем таблицу по вероятности в убывающем порядке

2) для каждого города в таблице генерируем случайное число от 1 до 100

3) если это число <= полю "вероятность" у данного города, то он попадает в список и удаляется из таблицы (чтобы не попасть в него ещё раз). В противном случае переходим к следующему городу.

Вот что получилось:

$cities = array( // Формат массива: (Уникальный номер города => Вероятность)

1 => 40,
2 => 20,
3 => 60,
4 => 50,
5 => 30,
6 => 10,
7 => 20,
8 => 20,
9 => 30,
10 => 40
);
arsort($cities);
$selected_cities = array();
while(count($selected_cities) < 5){
foreach($cities AS $id => $probability){
$random = rand(1, 100);
if($probability != null AND ($random <= $probability)){
$selected_cities[$id] = $probability;
$cities[$id] = null;
break;
}
}
}
able
На сайте с 25.03.2008
Offline
112
#4

nikitian, точно так же можно создать массив из 220 элементов и генерировать число от 0 до 219 :-)

Best regards.
[Удален]
#5
able:
nikitian, точно так же можно создать массив из 220 элементов и генерировать число от 0 до 219 :-)

поддерживаю)

[Удален]
#6
able:
nikitian, точно так же можно создать массив из 220 элементов и генерировать число от 0 до 219 :-)

Пропустил, что выводится не один, а 3 города. В случае одного города вероятность появления каждого города относительно него самого будет 50%: либо он, либо не он :)

[Удален]
#7
aleksey_php:
К сожалению, в моём случае речь всё-таки идёт именно о процентах, но проценты в таблице указываются не относительно других городов, а относительно двух состояний для одного города:
1. в списке
2. не в списке
Т.е. для города Москва есть 80% вероятность того, что он попадёт в список и его наличие в этом списке никак не влияет на возможность любого другого города попасть в этот список. Т.е. каждый город "сам за себя".
Пока писал этот пост родилось решение стоящего вопроса:
1) сортируем таблицу по вероятности в убывающем порядке
2) для каждого города в таблице генерируем случайное число от 1 до 100
3) если это число <= полю "вероятность" у данного города, то он попадает в список и удаляется из таблицы (чтобы не попасть в него ещё раз). В противном случае переходим к следующему городу.
Вот что получилось:
$cities = array( // Формат массива: (Уникальный номер города => Вероятность)
1 => 40,
2 => 20,
3 => 60,
4 => 50,
5 => 30,
6 => 10,
7 => 20,
8 => 20,
9 => 30,
10 => 40
);
arsort($cities);
$selected_cities = array();
while(count($selected_cities) < 5){
foreach($cities AS $id => $probability){
$random = rand(1, 100);
if($probability != null AND ($random <= $probability)){
$selected_cities[$id] = $probability;
$cities[$id] = null;
break;
}
}
}

А вам какое распределение нужно? =) Линейное, нормальное, Гауссово? ☝встроенный рандомайзер в php имеет нормальное распределение, засчет чего значения возле краев отрезка возвращаются гораздо реже чем в серединке, поэтому ваши проценты летят. Если говорить с точки зрения математики, то наиболее верным будет такое решение:


$cities = array( // Формат массива: (Уникальный номер города => Вероятность)
1 => 40,
2 => 20,
3 => 60,
4 => 50,
5 => 30,
6 => 10,
7 => 20,
8 => 20,
9 => 30,
10 => 40
);

$rand_array=array(); //генерация долевого массива
foreach ($cities as $id=>$count)
for ($i=0;$i<$count;$i++)
$rand_array[]=$id;
define("rand_iterations",10); //чем больше это число, тем более линейной получится выборка, но, естестванно, это экономически не выгодно.
for ($i=0;$i<rand_iterations;$i++) //перемешиваем долевой массив
shuffle($rand_array();
$result=array(); //генерация выходного массива
while (count($result)<3) //число - сколько городов вам надо. Надо ли говорить, что если их всего будет меньше, получите бесконечный цикл
{
$value=array_shift($rand_array);
if (in_array($value,$result))
continue;
$result[]=$value;
}

Довольно накладно, зато соответствие ваших долей истине обеспечено. В частности, если опять же математически, линейность распределения обеспечивается с точностью 99,5% для числа выборок не менее log(N)*A, где N это число перемешиваний массива, A - кол-во весовых элементов в нем. Т.е. если вы свои проценты тупо умножите на 10, то получите еще более точную вероятность, но и цена выполнения растет несколько быстрее - O(N*log(N))

Последний блок наверное можно попробовать заменить на

$result=array_slice(array_unique($rand_array),0,3);

При не очень больших весах будет быстрее

zhidronsss
На сайте с 12.10.2007
Offline
36
#8

проще создать массив с такой же плотностью элементов

москва

москва

москва

питер

питер

минск

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

$name=Array(...);

shuffle($name);
$name= array_unique($name);
print_r($name);
[Удален]
#9

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

Dweep
На сайте с 11.12.2006
Offline
207
#10
aleksey_php:
Есть таблица городов:
Название | Вероятность
Москва | 80%
Питер | 50%
Воронеж | 20%
Новосибирск | 20%
Урюпинск | 10%
Тольятти | 30%
Усть-Кулом | 10%


Необходимо выводить на странице 3 любых города из этой таблицы, но с учётом их вероятности. Т.е. при 10 обновлениях страницы мы увидим Москву, Питер и Тольятти чаще других, т.к. их вероятность попасть в случайный список больше, чем у остальных. Почему список случайный? Потому что он каждый раз формируется заново и, например, Москва попадёт в него, грубо говоря, в 8 случаях из 10.

Если кто-нибудь сталкивался с подобным, то подскажите как решить данную задачу.

Могут ли Ваши города в результате повторяться?

То есть результат

Москва

Москва

Москва

приемлем ?

Если не могут, то Ваша задача вывода с учетом вероятностей скорее всего принципиально не разрешима, так как тут уже идут уcловные события.

К примеру Задачу невозможно решить для верятностей

Москва | 99%

Питер | 1%

Воронеж | 1%

Новосибирск | 1%

Урюпинск | 1%

Тольятти | 1%

Так как приходится выбирать три города, и надо выбирать что то кроме Москвы, то по любому придется выбирать те города, вероятность выбора которых всего один процент, ну и в результате получится что остальные города фигурируют гораздо чаще.

У ваших коэффициентов та же самая проблема, просто ее трудней увидеть.

12

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий