Рубрики

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

Дано n чисел, каждое с некоторой частотой встречаемости. Вернуть случайное число с вероятностью, пропорциональной частоте его появления.

Пример:

Let following be the given numbers.
  arr[] = {10, 30, 20, 40}  

Let following be the frequencies of given numbers.
  freq[] = {1, 6, 2, 1}  

The output should be
  10 with probability 1/10
  30 with probability 6/10
  20 with probability 2/10
  40 with probability 1/10 

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

Нам нужно как-то трансформировать проблему в проблему, решение которой нам известно.

Один простой метод — взять вспомогательный массив (скажем, aux []) и продублировать числа в соответствии с частотой их появления. Создайте случайное число (скажем, r) от 0 до Sum-1 (включая оба), где Sum представляет суммирование частотного массива (freq [] в приведенном выше примере). Вернуть случайное число aux [r] (Реализация этого метода оставлена в качестве упражнения для читателей).

Ограничением вышеупомянутого способа, рассмотренного выше, является огромное потребление памяти при высокой частоте появления. Если ввод 997, 8761 и 1, этот метод явно неэффективен.

Как мы можем уменьшить потребление памяти? Ниже приведен подробный алгоритм, который использует O (n) дополнительного пространства, где n — количество элементов во входных массивах.

1. Возьмите вспомогательный массив (скажем, префикс []) размера n.
2. Заполните его префиксной суммой так, чтобы префикс [i] представлял сумму чисел от 0 до i.
3. Сгенерируйте случайное число (скажем, r) от 1 до Sum (включая оба), где Sum представляет собой суммирование массива входных частот.
4. Найдите индекс Ceil случайного числа, сгенерированного на шаге 3, в массиве префиксов. Пусть индекс будет индексом c .
5. Вернуть случайное число arr [indexc], где arr [] содержит введенные n чисел.

Прежде чем перейти к части реализации, давайте кратко рассмотрим алгоритм на следующем примере:
обр []: {10, 20, 30}
freq []: {2, 3, 1}
Префикс []: {2, 5, 6}
Поскольку последняя запись в префиксе равна 6, все возможные значения r равны [1, 2, 3, 4, 5, 6]
1: Ceil равен 2. Произведенное случайное число равно 10.
2: Ceil равен 2. Произведенное случайное число равно 10.
3: Ceil равно 5. Произведенное случайное число равно 20.
4: Ceil — 5. Произведенное случайное число — 20.
5: Ceil равно 5. Произведенное случайное число равно 20.
6. Ceil — 6. Сгенерированное случайное число — 30.
В приведенном выше примере
10 генерируется с вероятностью 2/6.
20 генерируется с вероятностью 3/6.
30 генерируется с вероятностью 1/6.

Как это работает?
Любое число input [i] генерируется столько раз, сколько его частота встречается, потому что в диапазоне существует число целых чисел (префикс [i — 1], префикс [i]] является input [i]. Как и в приведенном выше примере 3 генерируется трижды, так как существует 3 целых числа 3, 4 и 5, чей уровень равен 5.

C ++

// C ++ программа для генерации случайных чисел
// в соответствии с заданным распределением частоты
#include <bits/stdc++.h>

using namespace std;

  
// Сервисная функция для определения потолка r в arr [l..h]

int findCeil(int arr[], int r, int l, int h) 

    int mid; 

    while (l < h) 

    

        mid = l + ((h - l) >> 1); // То же, что и mid = (l + h) / 2

        (r > arr[mid]) ? (l = mid + 1) : (h = mid); 

    

    return (arr[l] >= r) ? l : -1; 

  
// Основная функция, которая возвращает случайное число
// из arr [] в соответствии с массивом распределения
// определяется freq []. n - размер массивов.

int myRand(int arr[], int freq[], int n) 

    // Создать и заполнить префиксный массив

    int prefix[n], i; 

    prefix[0] = freq[0]; 

    for (i = 1; i < n; ++i) 

        prefix[i] = prefix[i - 1] + freq[i]; 

  

    // префикс [n-1] является суммой всех частот.

    // Генерируем случайное число с

    // значение от 1 до этой суммы

    int r = (rand() % prefix[n - 1]) + 1; 

  

    // Находим индекс потолка r в префиксе arrat

    int indexc = findCeil(prefix, r, 0, n - 1); 

    return arr[indexc]; 

  
// Код драйвера

int main() 

    int arr[] = {1, 2, 3, 4}; 

    int freq[] = {10, 5, 20, 100}; 

    int i, n = sizeof(arr) / sizeof(arr[0]); 

  

    // Используйте разные начальные значения для каждого прогона.

    srand(time(NULL)); 

  

    // Давайте сгенерируем 10 случайных чисел согласно

    // данное распределение

    for (i = 0; i < 5; i++) 

    cout << myRand(arr, freq, n) << endl; 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для генерации случайных чисел в соответствии с заданным распределением частоты
#include <stdio.h>
#include <stdlib.h>

  
// Сервисная функция для определения потолка r в arr [l..h]

int findCeil(int arr[], int r, int l, int h)

{

    int mid;

    while (l < h)

    {

         mid = l + ((h - l) >> 1);  // То же, что и mid = (l + h) / 2

        (r > arr[mid]) ? (l = mid + 1) : (h = mid);

    }

    return (arr[l] >= r) ? l : -1;

}

  
// Основная функция, которая возвращает случайное число из arr [] согласно
// распределительный массив, определенный freq []. n - размер массивов.

int myRand(int arr[], int freq[], int n)

{

    // Создать и заполнить префиксный массив

    int prefix[n], i;

    prefix[0] = freq[0];

    for (i = 1; i < n; ++i)

        prefix[i] = prefix[i - 1] + freq[i];

  

    // префикс [n-1] является суммой всех частот. Генерация случайного числа

    // со значением от 1 до этой суммы

    int r = (rand() % prefix[n - 1]) + 1;

  

    // Находим индекс потолка r в префиксе arrat

    int indexc = findCeil(prefix, r, 0, n - 1);

    return arr[indexc];

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[]  = {1, 2, 3, 4};

    int freq[] = {10, 5, 20, 100};

    int i, n = sizeof(arr) / sizeof(arr[0]);

  

    // Используйте разные начальные значения для каждого прогона.

    srand(time(NULL));

  

    // Давайте сгенерируем 10 случайных чисел согласно

    // данное распределение

    for (i = 0; i < 5; i++)

      printf("%d\n", myRand(arr, freq, n));

  

    return 0;

}


Вывод: может быть разным для разных прогонов

4
3
4
4
4

Эта статья составлена Aashish Barnwal . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes