Generador de números aleatorios en forma de distribución de probabilidad arbitraria

Dados n números, cada uno con alguna frecuencia de ocurrencia. Devuelve un número aleatorio con probabilidad proporcional a su frecuencia de aparición.

Ejemplo: 

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

Está bastante claro que el generador de números aleatorios simple no funcionará aquí, ya que no realiza un seguimiento de la frecuencia de ocurrencia. 

Necesitamos transformar de alguna manera el problema en un problema cuya solución conozcamos.

Un método simple es tomar una array auxiliar (por ejemplo, aux[]) y duplicar los números según su frecuencia de aparición. Genere un número aleatorio (digamos r) entre 0 y Sum-1 (incluidos ambos), donde Sum representa la suma de la array de frecuencias (freq[] en el ejemplo anterior). Devuelve el número aleatorio aux[r] (La implementación de este método se deja como ejercicio para los lectores).

La limitación del método anterior discutido anteriormente es el enorme consumo de memoria cuando la frecuencia de ocurrencia es alta. Si la entrada es 997, 8761 y 1, este método claramente no es eficiente.

¿Cómo podemos reducir el consumo de memoria? El siguiente es un algoritmo detallado que usa O(n) espacio adicional donde n es el número de elementos en las arrays de entrada.
1. Tome una array auxiliar (digamos prefijo []) de tamaño n. 
2. Rellénelo con el prefijo suma, de modo que el prefijo[i] represente la suma de números del 0 al i. 
3. Genere un número aleatorio (por ejemplo, r) entre 1 y Sum (incluidos ambos), donde Sum representa la suma de la array de frecuencia de entrada. 
4. Encuentre el índice de Ceil de número aleatorio generado en el paso 3 en la array de prefijos. Sea el índice el índice c . 
5. Devuelve el número aleatorio arr[indexc], donde arr[] contiene los n números de entrada.
  Antes de pasar a la parte de implementación, echemos un vistazo rápido al algoritmo con un ejemplo: 
      arr[]: {10, 20, 30} 
      freq[]: {2, 3, 1} 
      Prefix[]: {2, 5 , 6} 
  Dado que la última entrada en el prefijo es 6, todos los valores posibles de r son [1, 2, 3, 4, 5, 6] 
         1: el techo es 2. El número aleatorio generado es 10. 
         2: el techo es 2. Número aleatorio generado es 10. 
         3: el techo es 5. El número aleatorio generado es 20. 
         4: el techo es 5. El número aleatorio generado es 20. 
         5: el techo es 5. El número aleatorio generado es 20. 
         6. El techo es 6. El número aleatorio generado es 30. 
  En el ejemplo anterior 
      , 10 se genera con una probabilidad de 2/6. 
      20 se genera con probabilidad 3/6. 
      30 se genera con probabilidad 1/6.

¿Como funciona esto?  
Cualquier entrada de número[i] se genera tantas veces como su frecuencia de ocurrencia porque existe un conteo de enteros en el rango (prefijo[i – 1], prefijo[i]] es entrada[i]. Como en el ejemplo anterior, 3 es generado tres veces, ya que existen 3 enteros 3, 4 y 5 cuyo techo es 5. 

// C++ program to generate random numbers
// according to given frequency distribution
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find ceiling of r in arr[l..h]
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 array
    int indexc = findCeil(prefix, r, 0, n - 1);
    return arr[indexc];
}
 
// Driver code
int main()
{
    int arr[] = {1, 2, 3, 4};
    int freq[] = {10, 5, 20, 100};
    int i, n = sizeof(arr) / sizeof(arr[0]);
 
    // Use a different seed value for every run.
    srand(time(NULL));
 
    // Let us generate 10 random numbers according to
    // given distribution
    for (i = 0; i < 5; i++)
    cout << myRand(arr, freq, n) << endl;
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

//C program to generate random numbers according to given frequency distribution
#include <stdio.h>
#include <stdlib.h>
 
// Utility function to find ceiling of r in arr[l..h]
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 array
    int indexc = findCeil(prefix, r, 0, n - 1);
    return arr[indexc];
}
 
// Driver program to test above functions
int main()
{
    int arr[]  = {1, 2, 3, 4};
    int freq[] = {10, 5, 20, 100};
    int i, n = sizeof(arr) / sizeof(arr[0]);
 
    // Use a different seed value for every run.
    srand(time(NULL));
 
    // Let us generate 10 random numbers according to
    // given distribution
    for (i = 0; i < 5; i++)
      printf("%d\n", myRand(arr, freq, n));
 
    return 0;
}

// Java program to generate random numbers
// according to given frequency distribution
class GFG
{
 
// Utility function to find ceiling of r in arr[l..h]
static 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
        if(r > arr[mid])
            l = mid + 1;
        else
            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.
static int myRand(int arr[], int freq[], int n)
{
    // Create and fill prefix array
    int prefix[] = new int[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 = ((int)(Math.random()*(323567)) % prefix[n - 1]) + 1;
 
    // Find index of ceiling of r in prefix array
    int indexc = findCeil(prefix, r, 0, n - 1);
    return arr[indexc];
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = {1, 2, 3, 4};
    int freq[] = {10, 5, 20, 100};
    int i, n = arr.length;
 
    // Let us generate 10 random numbers according to
    // given distribution
    for (i = 0; i < 5; i++)
    System.out.println( myRand(arr, freq, n) );
}
}
 
// This code is contributed by Arnab Kundu

# Python3 program to generate random numbers
# according to given frequency distribution
import random
 
# Utility function to find ceiling of r in arr[l..h]
def findCeil(arr, r, l, h) :
 
    while (l < h) :   
        mid = l + ((h - l) >> 1); # Same as mid = (l+h)/2
        if r > arr[mid] :
            l = mid + 1
        else :
            h = mid
     
    if arr[l] >= r :
        return l
    else :
        return -1
 
# The main function that returns a random number
# from arr[] according to distribution array
# defined by freq[]. n is size of arrays.
def myRand(arr, freq, n) :
 
    # Create and fill prefix array
    prefix = [0] * n
    prefix[0] = freq[0]
    for i in range(n) :
        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
    r = random.randint(0, prefix[n - 1]) + 1
 
    # Find index of ceiling of r in prefix array
    indexc = findCeil(prefix, r, 0, n - 1)
    return arr[indexc]
 
# Driver code
arr = [1, 2, 3, 4]
freq = [10, 5, 20, 100]
n = len(arr)
 
# Let us generate 10 random numbers according to
# given distribution
for i in range(5) :
    print(myRand(arr, freq, n))
 
    # This code is contributed by divyesh072019

// C# program to generate random numbers
// according to given frequency distribution
using System;
 
class GFG{
     
// Utility function to find ceiling
// of r in arr[l..h] 
static int findCeil(int[] arr, int r,
                    int l, int h) 
{ 
    int mid;
    while (l < h) 
    { 
         
        // Same as mid = (l+h)/2 
        mid = l + ((h - l) >> 1);
         
        if (r > arr[mid]) 
            l = mid + 1;
        else
            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. 
static int myRand(int[] arr, int[] freq, int n) 
{ 
     
    // Create and fill prefix array 
    int[] prefix = new int[n];
    int 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
    Random rand = new Random();
    int r = ((int)(rand.Next() * (323567)) %
                      prefix[n - 1]) + 1; 
   
    // Find index of ceiling of r in prefix array 
    int indexc = findCeil(prefix, r, 0, n - 1); 
    return arr[indexc]; 
}
 
// Driver Code
static void Main()
{
    int[] arr = { 1, 2, 3, 4 }; 
    int[] freq = { 10, 5, 20, 100 }; 
    int i, n = arr.Length; 
     
    // Let us generate 10 random numbers
    // according to given distribution 
    for(i = 0; i < 5; i++) 
        Console.WriteLine(myRand(arr, freq, n)); 
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// JavaScript program to generate random numbers
// according to given frequency distribution
 
    // Utility function to find ceiling of r in arr[l..h]
    function findCeil(arr, r, l, h)
    {
        let 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.
    function myRand(arr, freq,  n) {
        // Create and fill prefix array
        let prefix= [];
        let 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
        let r = Math.floor((Math.random()* prefix[n - 1])) + 1;
 
        // Find index of ceiling of r in prefix array
        let indexc = findCeil(prefix, r, 0, n - 1);
        return arr[indexc];
    }
 
    // Driver code
    let arr = [1, 2, 3, 4];
    let freq = [10, 5, 20, 100];
    let i;
    let n = arr.length;
 
    // Use a different seed value for every run.
 
    // Let us generate 10 random numbers according to
    // given distribution
    for (i = 0; i < 5; i++)
      document.write(myRand(arr, freq, n));
       
      // This code is contributed by rohitsingh07052.
</script>

Salida: puede ser diferente para diferentes ejecuciones 

4
3
4
4
4

Complejidad de tiempo: O(n)

Este artículo ha sido compilado por Aashish Barnwal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.