Dada una secuencia de números, genere un número aleatorio a partir de la secuencia. Puede usar solo el espacio O (1) y la entrada tiene la forma de una secuencia, por lo que no puede almacenar los números vistos anteriormente.
Entonces, ¿cómo generamos un número aleatorio de todo el flujo de modo que la probabilidad de elegir cualquier número sea 1/n? con O(1) espacio extra? Este problema es una variación del muestreo de yacimientos . Aquí el valor de k es 1.
1) Inicializar ‘contar’ como 0, ‘contar’ se usa para almacenar el conteo de números vistos hasta ahora en la transmisión.
2) Para cada número ‘x’ del flujo, haga lo siguiente
… a) Incremente ‘recuento’ en 1.
…. b) Si el conteo es 1, establezca el resultado como x y devuelva el resultado.
…..c )Genere un número aleatorio de 0 a ‘contar-1’. Sea i el número aleatorio generado.
….. d) Si i es igual a ‘cuenta – 1’, actualice el resultado como x.
C++
// An efficient C++ program to randomly select
// a number from stream of numbers.
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
// A function to randomly select a item
// from stream[0], stream[1], .. stream[i-1]
int selectRandom(int x)
{
static int res; // The resultant random number
static int count = 0; // Count of numbers visited
// so far in stream
count++; // increment count of numbers seen so far
// If this is the first element from stream,
// return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
int i = rand() % count;
// Replace the prev random number with
// new number with 1/count probability
if (i == count - 1)
res = x;
}
return res;
}
// Driver Code
int main()
{
int stream[] = {1, 2, 3, 4};
int n = sizeof(stream) / sizeof(stream[0]);
// Use a different seed value for every run.
srand(time(NULL));
for (int i = 0; i < n; ++i)
cout << "Random number from first " << i + 1
<< " numbers is " << selectRandom(stream[i]) << endl;
return 0;
}
// This is code is contributed by rathbhupendra
C
// An efficient C program to randomly select a number from stream of numbers.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// A function to randomly select a item from stream[0], stream[1], .. stream[i-1]
int selectRandom(int x)
{
static int res; // The resultant random number
static int count = 0; //Count of numbers visited so far in stream
count++; // increment count of numbers seen so far
// If this is the first element from stream, return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
int i = rand() % count;
// Replace the prev random number with new number with 1/count probability
if (i == count - 1)
res = x;
}
return res;
}
// Driver program to test above function.
int main()
{
int stream[] = {1, 2, 3, 4};
int n = sizeof(stream)/sizeof(stream[0]);
// Use a different seed value for every run.
srand(time(NULL));
for (int i = 0; i < n; ++i)
printf("Random number from first %d numbers is %d \n",
i+1, selectRandom(stream[i]));
return 0;
}
Java
//An efficient Java program to randomly select a number from stream of numbers.
import java.util.Random;
public class GFG
{
static int res = 0; // The resultant random number
static int count = 0; //Count of numbers visited so far in stream
//A method to randomly select a item from stream[0], stream[1], .. stream[i-1]
static int selectRandom(int x)
{
count++; // increment count of numbers seen so far
// If this is the first element from stream, return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
Random r = new Random();
int i = r.nextInt(count);
// Replace the prev random number with new number with 1/count probability
if(i == count - 1)
res = x;
}
return res;
}
// Driver program to test above function.
public static void main(String[] args)
{
int stream[] = {1, 2, 3, 4};
int n = stream.length;
for(int i = 0; i < n; i++)
System.out.println("Random number from first " + (i+1) +
" numbers is " + selectRandom(stream[i]));
}
}
//This code is contributed by Sumit Ghosh
Python3
# An efficient python3 program
# to randomly select a number
# from stream of numbers.
import random
# A function to randomly select a item
# from stream[0], stream[1], .. stream[i-1]
# The resultant random number
res=0
# Count of numbers visited
# so far in stream
count=0
def selectRandom(x):
global res
global count
# increment count of numbers
# seen so far
count += 1;
# If this is the first element
# from stream, return it
if (count == 1):
res = x;
else:
# Generate a random number
# from 0 to count - 1
i = random.randrange(count);
# Replace the prev random number
# with new number with 1/count
# probability
if (i == count - 1):
res = x;
return res;
# Driver Code
stream = [1, 2, 3, 4];
n = len(stream);
# Use a different seed value
# for every run.
for i in range (n):
print("Random number from first",
(i + 1), "numbers is",
selectRandom(stream[i]));
# This code is contributed by mits
C#
// An efficient C# program to randomly
// select a number from stream of numbers.
using System;
class GFG
{
// The resultant random number
static int res = 0;
// Count of numbers visited
// so far in stream
static int count = 0;
// A method to randomly select
// a item from stream[0],
// stream[1], .. stream[i-1]
static int selectRandom(int x)
{
// increment count of
// numbers seen so far
count++;
// If this is the first
// element from stream,
// return it
if (count == 1)
res = x;
else
{
// Generate a random number
// from 0 to count - 1
Random r = new Random();
int i = r.Next(count);
// Replace the prev random
// number with new number
// with 1/count probability
if(i == count - 1)
res = x;
}
return res;
}
// Driver Code
public static void Main()
{
int[] stream = {1, 2, 3, 4};
int n = stream.Length;
for(int i = 0; i < n; i++)
Console.WriteLine("Random number from " +
"first {0} numbers is {1}" ,
i + 1, selectRandom(stream[i]));
}
}
// This code is contributed by mits
PHP
<?php
// An efficient php program to randomly
// select a number from stream of numbers.
// A function to randomly select a item
// from stream[0], stream[1], .. stream[i-1]
function selectRandom($x)
{
// The resultant random number
$res;
// Count of numbers visited so far
// in stream
$count = 0;
// increment count of numbers seen
// so far
$count++;
// If this is the first element
// from stream, return it
if ($count == 1)
$res = $x;
else
{
// Generate a random number from
// 0 to count - 1
$i = rand() % $count;
// Replace the prev random number
// with new number with 1/count
// probability
if (i == $count - 1)
$res = $x;
}
return $res;
}
// Driver program to test above function.
$stream = array(1, 2, 3, 4);
$n = sizeof($stream)/sizeof($stream[0]);
// Use a different seed value for
// every run.
srand(time(NULL));
for ($i = 0; $i < $n; ++$i)
echo "Random number from first ",
$i+1, "numbers is " ,
selectRandom($stream[$i]), "\n" ;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
//An efficient Javascript program to randomly select a number from stream of numbers.
let res = 0; // The resultant random number
let count = 0; //Count of numbers visited so far in stream
//A method to randomly select a item from stream[0], stream[1], .. stream[i-1]
function selectRandom(x)
{
count++; // increment count of numbers seen so far
// If this is the first element from stream, return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
let i = Math.floor(Math.random()*(count));
// Replace the prev random number with new number with 1/count probability
if(i == count - 1)
res = x;
}
return res;
}
// Driver program to test above function.
let stream=[1, 2, 3, 4];
let n = stream.length;
for(let i = 0; i < n; i++)
document.write("Random number from first " + (i+1) + " numbers is " + selectRandom(stream[i])+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Random number from first 1 numbers is 1 Random number from first 2 numbers is 1 Random number from first 3 numbers is 3 Random number from first 4 numbers is 4
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
¿Cómo funciona esto
? Necesitamos demostrar que cada elemento se elige con una probabilidad de 1/n, donde n es el número de elementos vistos hasta el momento. Para cada nuevo elemento de flujo x, elegimos un número aleatorio de 0 a ‘cuenta -1’, si el número elegido es ‘cuenta-1’, reemplazamos el resultado anterior con x.
Para simplificar la prueba, primero consideremos el último elemento, el último elemento reemplaza el resultado previamente almacenado con una probabilidad de 1/n. Entonces, la probabilidad de obtener el último elemento como resultado es 1/n.
Hablemos ahora del penúltimo elemento. Cuando el penúltimo elemento se procesó la primera vez, la probabilidad de que reemplazó al resultado anterior es 1/(n-1). La probabilidad de que el resultado anterior se mantenga cuando se considera el n-ésimo elemento es (n-1)/n. Entonces, la probabilidad de que el penúltimo elemento se elija en la última iteración es [1/(n-1)] * [(n-1)/n], que es 1/n.
Del mismo modo, podemos probar para el tercer último elemento y otros.
Referencias:
Muestreo de yacimientos
Método 2: genera un número aleatorio a partir de la secuencia con el método numpy random.choice().
Python3
import numpy as np
# initializing list
stream = [1, 4, 5, 2, 7]
# using random.choice() to
# get a random number
random_num = np.random.choice(stream)
# printing random number
print("random number is ",random_num)
Producción:
7
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA