Random number generator in arbitrary probability distribution fashion | GeeksforGeeks
Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.
O(n) Space
1. Take an auxiliary array (say prefix[]) of size n.
2. Populate it with prefix sum, such that prefix[i] represents sum of numbers from 0 to i.
3. Generate a random number(say r) between 1 to Sum(including both), where Sum represents summation of input frequency array.
4. Find index of Ceil of random number generated in step #3 in the prefix array. Let the index be indexc.
5. Return the random number arr[indexc], where arr[] contains the input n numbers.
Read full article from Random number generator in arbitrary probability distribution fashion | GeeksforGeeks
Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.
O(n) Space
1. Take an auxiliary array (say prefix[]) of size n.
2. Populate it with prefix sum, such that prefix[i] represents sum of numbers from 0 to i.
3. Generate a random number(say r) between 1 to Sum(including both), where Sum represents summation of input frequency array.
4. Find index of Ceil of random number generated in step #3 in the prefix array. Let the index be indexc.
5. Return the random number arr[indexc], where arr[] contains the input n numbers.
int
findCeil(
int
arr[],
int
r,
int
l,
int
h)
{
int
mid;
while
(l < h)
{
mid = l + ((h - l) >> 1);
// Same as mid = (l+h)/2
(r > arr[mid]) ? (l = mid + 1) : (h = mid);
}
return
(arr[l] >= r) ? l : -1;
}
// The main function that returns a random number from arr[] according to
// distribution array defined by freq[]. n is size of arrays.
int
myRand(
int
arr[],
int
freq[],
int
n)
{
// Create and fill prefix array
int
prefix[n], i;
prefix[0] = freq[0];
for
(i = 1; i < n; ++i)
prefix[i] = prefix[i - 1] + freq[i];
// prefix[n-1] is sum of all frequencies. Generate a random number
// with value from 1 to this sum
int
r = (
rand
() % prefix[n - 1]) + 1;
// Find index of ceiling of r in prefix arrat
int
indexc = findCeil(prefix, r, 0, n - 1);
return
arr[indexc];
}
One simple method is to take an auxiliary array (say aux[]) and duplicate the numbers according to their frequency of occurrence. Generate a random number(say r) between 0 to Sum-1(including both), where Sum represents summation of frequency array (freq[] in above example). Return the random number aux[r] (Implementation of this method is left as an exercise to the readers).
The limitation of the above method discussed above is huge memory consumption when frequency of occurrence is high.