array = {-10, 3, 9, 0, 111, 99}
and probability distribution
distr = {0.07, 0.2, 0.1, 0.33, 0.07, 0.23}
Can you write C/C++ code (not using C++11) that will guarantee (more or less) that
nextVal() function will return randomly next value from array with given probability ?
So it means after 100 executions of nextVal more or less you should see that nextVal numbers are aligned with probability distribution: perfectly (7,20,10,33,7,23) .
It is an easy task but if you are struggled , feel free and take a look (it's not optimized):
#include <iostream>
#include <cmath>
#include <time.h>
#include <stdlib.h>
#include <map>
#include <vector>
using namespace std;
#define ARRAY_SIZE(array) (sizeof(array)/sizeof(array[0]))
int checkDistribution(double random, const map<double, vector<int> > &distribution_map)
{
int index = 0;
map<double, vector<int> >::const_iterator it = distribution_map.begin();
for (; it!=distribution_map.end(); ++it)
{
if (random < (*it).first)
{
int randomInternal = 0;
if ((*it).second.size() > 1)
randomInternal = rand() % ((*it).second.size());
index = (*it).second.at(randomInternal);
break;
}
}
return index;
}
void nextNum(int* results, const map<double, vector<int> > &distribution_map)
{
double random = (double) rand()/RAND_MAX;
int index = checkDistribution(random,distribution_map);
results[index]+=1;
}
int main() {
srand (time(NULL));
int results [] = {0,0,0,0,0};
int numbers [] = {-1,0,1,2,3};
double prob [] = {0.01, 0.3, 0.58, 0.1, 0.01};
int size = ARRAY_SIZE(numbers);
// Building Distribution
map<double, vector<int> > distribution_map;
map<double, vector<int> >::iterator it;
for (int i = 0; i < size; i++)
{
it = distribution_map.find(prob[i]);
if (it!=distribution_map.end())
it->second.push_back(i);
else
{
vector<int> vec;
vec.push_back(i);
distribution_map[prob[i]] = vec;
}
}
// PDF to CDF transform
map<double, vector<int> > cumulative_distribution_map;
map<double, vector<int> >::iterator iter_cumulative;
double cumulative_distribution = 0.0;
for (it=distribution_map.begin();it!=distribution_map.end();++it)
{
cumulative_distribution += ((*it).second.size() * (*it).first);
cumulative_distribution_map[cumulative_distribution] = (*it).second;
}
for (int i = 0; i<100; i++)
{
nextNum(results, cumulative_distribution_map);
}
for (int j = 0; j<size; j++)
cout<<" "<<results[j]<<" ";
return 0;
}
