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. 

Read full article from Random number generator in arbitrary probability distribution fashion | GeeksforGeeks