numeros aleatoriios sin repetir

[[Delphius]]

Empezado por mamcx

Ten en cuenta que RANDOM *no signifca* que la distribucion es *uniforme*.

Es totalmente posible que una funcion random genere un millon de veces el *mismo* numero.

De hecho, una funcion random real se graficaria y daria que hay varios "clusters" alrededor de un grupo de numeros, sin que haya una distribucion perfecta de las posiblidades.

--
* Asumiendo que el codigo este bien hecho y no altere aun mas los resultados.

FALSO.
Las funciones Random si son uniformes. Todas* tienen la misma probabilidad de salir: 1/m siendo m el período que tenga el generador.

*Todas las que se precien, y que están bien implementadas. Tenemos los clásicos generadores congruencial mixto y/o multiplicativo, como el gran generador MT19937N que es una implementación de Mersenne Twister; ampliamente probado y que está implementado como base en muchos lenguajes. Entre ellos: Lazarus. Delphi que yo sepa sigue usando un congruencial mixto.

Y digo que son uniformes porque fueron pensadas para generar números en el rango [0, 1)
Estas funciones random luego se deben volcar en la distribución que uno necesite para generar las Variables Aleatorias que pretende recrear o simular, calcular, etc. Por ejemplo, se puede usar una distribución normal, una uniforme, una exponencial, etc. Todas estas toman el valor R (random) y aplica el algoritmo de la función inversa acumulada F de dicha distribución. Por ejemplo para el caso de una distribución uniforme:

Código Delphi [-]
function Uniform(A, B: double): double;
var R: double;
begin
  R := random; // obtenemos un valor pseudo aleatorio en el rango [0,1)
  result := A + R * (B - A); // expresamos ahora R en la distribución para el rango [A,B]
end;

Y para la distribución normal es un poco más complicada, ya no la recuerdo muy bien... no me animo a poner un código realmente no vaya a ser cosa que le pifie. Recuerdo de un método relativamente rápido y lo suficiente preciso para la mayoría de las situaciones, e inspirado en la teoría del límite central.
Se calculaba la suma de 6 u 12 (no recuerdo bien) valores R, y luego se procedía a ¿multiplicar? por el valor de la desviación estándar pasado como parámetro. Era un algoritmo relativamente simple.

Como es de esperar, las variables aleatorias obtenidas con esta distribución seguirán la forma normal.

Y así, es para cada distribución que uno quiera.
En términos abstractos, matemáticamente tenemos VA = F(p1...pN, GEN);
Siendo VA la Variable Aletoria
F la función inversa para la distribución que uno requiera
p1 a pN los parámetros que requiere la distribución
GEN la función generadora de números pseudoaletorios [0,1)

Los repetidos que uno observa cuando hace uso de random en Delphi o en cualquier otro lenguaje se debe a que:

1. Está acotando el rango de secuencia a adoptar un valor mucho más chico. Por ejemplo, cuando "yo quiero números aletorios entre 1 y 50" random(50) lo que hará es traducir esos decimales infinitos a un rango finito. Este ejemplo es un tipico caso de una uniforme (A = 1, B = 50). Si en lugar de que el rango sea 50 sino un número mucho más grande.... 10^32 por ejemplo estos decimales entre 0 y 1 aportan mucho más riqueza y la probabilidad de encontrar repetidos disminuye.

2. O ha generado tantos números que se ha completado la secuencia de m-1 números distintos que es capaz de generar. Este m es un valor bastante grande. Un generador bien planteado, generará m-1 números distintos (insisto... si toma el valor R en 0..1 en su concepción infinita... recordemos que la aritemética de punto flotante tiene precisión finita) y empezará el nuevo ciclo (la misma secuencia) a partir del m-esimo número.

Mamx por favor evita pasar estas vergüenzas, no es bueno que tenga que estar corrigiendote seguido. Confundes al chico. A repasar se ha dicho... yo también que ya no recuerdo el algoritmo para la distribución normal.

Saludos,