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，注意不要搞错。

# 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;
}

}
``````