Non Uniform Random Number

EPI 6.15

Geeks

Description:

Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.

Example:

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

Idea:

1. 已知probability的histogram，计算prefix sum
2. 知道一共多少个，假设是k个
3. 用rand()得到一个[1, k]的随机数，查找prefix sum array里对应的index，用二分法

findCeiling()类似upper bound search，注意不要搞错。

如果给的不是frequency而是probability，也可以用类似的方法做。

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;


class NonUniformRandom 
{
public:
    NonUniformRandom(vector<int> arr, vector<int> frequency)
    : arr(arr)
    , freq(frequency)
    , prefixSum(frequency) {
        for(int i=1; i<prefixSum.size(); i++){
            prefixSum[i] = prefixSum[i-1]+freq[i];
        }
    }    

    int getRandomNumber() const{
        int rndNum = rand()%prefixSum.back() + 1;
        int indx = findCeiling(rndNum);
        return arr[indx];
    }

private:
    // Similar to upper bound search
    int findCeiling(int randNumber) const {
        int begin=0;
        int end=arr.size();
        int mid;
        while(begin<end){
            mid = begin + (end-begin)/2;
            if(prefixSum[mid] == randNumber){
                return mid;
            }
            else if(prefixSum[mid]<randNumber){
                begin = mid+1;
            }
            else{
                end = mid;
            }
        }
        return begin;
    }

    vector<int> arr;
    vector<int> freq;
    vector<int> prefixSum;
};

int main(){
    vector<int> arr={10, 30, 20, 40};
    vector<int> freq={1, 6, 2, 1};

    NonUniformRandom nonUniformRnd(arr, freq);

    unordered_map<int, int> countDict;

    int totalRun=10000;
    for(int i=0; i<totalRun; i++){
        int num= nonUniformRnd.getRandomNumber();
        countDict[num] += 1;
    } 

    for(auto elem: countDict){
        cout<<elem.first<<' '<<elem.second/(totalRun*1.0)<<endl;
    }

}