Генератор псевдослучайных чисел с зависимой вероятностью вывода нужных чисел?

Есть задача:


На основе каких-нибудь готовых средств или функций (например, rand) нужно сделать функцию, которая будет возвращать по заданному диапазону (или готовому набору каких-то чисел) псевдослучайные числа, причем не равномерно, а по какой-то задаваемой зависимости. В качестве базовой можно взять следующую зависимость: возвращать чаще большие значения. При этом возникает резонный вопрос, насколько чаще. Тут также предлагается какой-нибудь любой задаваемый вариант, например, во столько раз чаще, насколько порядковый номер данного элемента в массиве больше.


Пример:


Массив m = [1, 3, 7, 19]. Мы вызываем нашу функцию getMyRand() передавая в нее массив (или диапазон, если нет массива). В результате получаем какие-то такие значения (номер вызова функции — возвращенное значение):


1 — 19

2 — 7

3 — 19

4 — 19

5 — 3

6 — 19

7 — 7

8 — 1

9 — 19

10 — 7

11 — 19

12 — 7

13 — 3

14 — 19

15 — 19

и т.д.


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


Чем она может быть интересна? Например, написать бота, который будет посещать сайты и симулировать просмотры страниц близко к поведению человека.
  • Вопрос задан
  • 15586 просмотров
Пригласить эксперта
Ответы на вопрос 6
dlinyj
@dlinyj
Элементарно Ватсон, вам нужна функция, которая будет давать случайные числа с заданным распределением.
Например:

возвращать чаще большие значения
— это экспоненциальная, или показательная функция. Я как-то занимался данным вопросом. Вам нужно сделать обратное преобразование функции распределения и просто подставлять туда свои значения и на выходе иметь с нужным распределением.
Ответ написан
StanSemenoff
@StanSemenoff Автор вопроса
Написал быстрый тестовый скрипт на PHP:

<?php
$m = [];
for ($i = 0; $i < 1000; $i++)
{
	$rnd = (int) (10 * log(rand(3, 50)));
	$m[$rnd] = isset($m[$rnd]) ? $m[$rnd] + 1 : 0;
}
ksort($m);
foreach ($m as $i => $cnt)
    echo "<div style='margin: 2px; color: #fff; padding: 3px; background: #696; width: ".($cnt * 10)."px;'>$i</div>\n";
?>

Ответ написан
Stdit
@Stdit
Я когда-то делал генератор псч с произвольным распределением через хэш-функцию. Алгоритм лобовой, на математическую и техническую красоту не претендует, но все равно я его опишу, вдруг кому-то пригодится.

— Нам нужен генератор псч, скажем от 0 до 99 с варьируемой вероятностю выпадения чисел.
— Заводим массив из 10000 элементов. Все числа заносим в массив по 100 раз.
— Выбирая из массива число со случайным (через обычный гпсч) индексом от 0 до 9999, мы получим число от 0 до 99 с равной вероятностью.
— Для уменьшения вероятности выпадения числа нужно уменьшить количество этих чисел в массиве. Например, если число «8» будет входить в массив не 100, а 50 раз — то его вероятность выпадения будет вдвое ниже, чем остальных.
— Для увеличения вероятности выпадения числа расширяем массив и добавляем ещё таких чисел.

Таким образом, можно построить почти любую функцию распределения (разумеется, с ограничениями на коэффициенты вероятности выпадения чисел). Плавность растройки такого генератора напрямую зависит от размера массива.
Ответ написан
@morincer
Для варианта конечной дискретной последовательности (как в Вашем случае) задача решается достаточно просто вариацией метода Монте-Карло.

Допустим у нас есть массив A натуральных чисел от 0 до n (0, 1, ..., n — 1) и для каждого из этих чисел задана вероятность его генерации p(a_i) (естественно, сумма всех вероятностей равна 1). Идея метода: разделить отрезок [0;1) на n отрезков, длина каждого из которых равна вероятности появления соответствующего числа из массива А. Далее, уже стандартным генератором ПСЧ выбираем число в диапазоне [0;1) и проверяем в какой из отрезков оно попало. Соответствующий данному отрезку элемент исходного массива возвращаем в качестве результата работы нашего генератора.
Реализацию алгоритма оставим читателю в качестве домашнего задания :)
Ответ написан
bloodyvlad
@bloodyvlad
Мое тупое, но рабочее решение описано тут habrahabr.ru/post/194598/ — доработанную версию использовал в последнем проекте. Генерирует все по моим правилам, быстро и четко.
Ответ написан
Комментировать
bloodyvlad
@bloodyvlad
перенес в QA — habrahabr.ru/qa/47196/
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы