Stratos: Punto de Encuentro de Desarrolladores

¡Bienvenido a Stratos!

Acceder

Foros





Numeros aleatorios

Iniciado por Altair, 12 de Mayo de 2011, 09:24:37 AM

« anterior - próximo »

Altair

Muy buenas,

estoy mirando con mas detalle el tema de los numeros aleatorios usando C/C++ y  me he encontrado lo siguiente:

Para la semilla:
srand(time(NULL));

Para numeros aleatorios entre un MIN y un MAX que sean distintos de cero, formulas a montones:
rand () % (N-M+1) + M; // N es el max y M el min
P+(int)(((U-P+1.0)*rand())/(RAND_MAX+1.0)); // U y P son dos numeros cualesquiera
max_value%rand())+ min_value;

Problema: estoy haciendo pruebas con una funcion que dibuja lineas horizontales en la pantalla, y por lo visto algo falla porque veo muchos azules y verdes pero poco mas. Algun amarillo perdido, y creo que no he visto aun ningun rojo ni otros colores.

Opcion A: la formula de semilla esta mal. Lo malo de esta opcion es que me la he encontrado en mil sitios. Otra posibilidad es hacerlo tomando como base la fecha+hora actual del sistema, pero CREO que no necesito tanta precision.

Opcion B: la formula del rand esta mal. Lo que pasa con estas formulas es que esta el factor de hasta que punto queremos que sean aleatorios. ¿Buscamos que no se repitan nunca o casi nunca o eso es mas bien poco importante y no pasa "nada" si la secuencia se repite?. Tal vez por este factor es por el que algunas formulas son mas elaboradas que otras.

Dado que estoy usando colores RGB, los valores van de 0 a 255. Para las pruebas le pido a rand un valor entre 1 y 255. Siempre los mismos azules y verdes, ponga la formula que ponga. Seguramente sea una tonteria, pero no caigo.

Hechelion

Aleatorio no significa que se repita o no, porque se supone que estás trabajando en un sistema sin memoria, un mismo valor se puede repetir cien veces y aún así tener un sistema aleatorio. (Que un mismo valor se repita 100 es una probabilidad de todas las posibles).

Un sistema aleatorio uniforme, como un dado, a largo plazo tenderá a tener una distribución uniforme para todo el recorrido, pero en el corto plazo puede presentar cualquier comportamiento.

Si tiramos 3 dados, y en las 3 tiradas sale un 6 es un comportamiento completamente posible (1 de 27 ocasiones saldrá). y sigue siendo un sistema aleatorio.


Volviendo a tu pregunta, ninguna de las formulas que presentas, modifica la distribución, solo son diferentes maneras de volcar el resultado del Rand() en el valor que necesitas pero nada más. No hay error ni en las formulas que presentas ni la semilla.
rand tiende a presentar una distribución no del todo homogénea, ya que los números bajos tienden a ser algo más propensos.

Lo que acá tendríamos que revisar es tu formula para obtener el color, ya que ahí puede estar el problema, a lo mejor, sin querer, estás cambiando la distribución.

Phoer

Con esto buscas una función que te dé números aleatorios no repetidos? Si es así, se podría plantear dos soluciones:

- Buscar un número aleatorio y, antes de meterlo en un vector, recorrer el mismo para comprobar que el número aleatorio no ha salido previamente.
- Meter todos los valores distintos en un vector, que la función rand() te saque un valor entre 0 y el tamaño del vector, meter el valor en otro vector y eliminarlo del primero.

La primera solución va bien siempre y cuando no quieras sacar muchos valores distintos y si la diferencia del rango [en este caso, del 0 al 255] es bastante grande [que lo es], pero si lo que quieres son muchos valores aleatorios sin que se repita ninguno de ellos, la mejor opción es la segunda. Quizás te parezca un poco lío, pero si es lo que buscas, en cuanto pueda te pongo el código de una función que hice tiempo ha, que va como la seda ;)

Vicente

No estaras llamando a srand(time(NULL)); varias veces no?

Phoer

Problemas comunes son el que planteas tu, Vicente, o que, al iniciar la aplicación, siempre obtendremos los mismos números. Por ello es aconsejable tener en cuenta la hora del sistema

shephiroth

Buenas.

Primero, respecto a las formulas
Cita de: Altair en 12 de Mayo de 2011, 09:24:37 AMrand () % (N-M+1) + M; // N es el max y M el min
P+(int)(((U-P+1.0)*rand())/(RAND_MAX+1.0)); // U y P son dos numeros cualesquiera
max_value%rand())+ min_value;
- La primera decirte que es rand() * y no %
- La segunda, depende del compilador aunque uncluye numeros double puede que no haga el cast adecuadamente. Yo prefiero definir U y P como float y hacer cast a int al resultado a la hora de usarlo....int res = (int)(.....);
- En la tercera, denuevo * en vez de %

Cita de: Hechelion en 12 de Mayo de 2011, 11:13:22 AMSi tiramos 3 dados, y en las 3 tiradas sale un 6 es un comportamiento completamente posible (1 de 27 ocasiones saldrá). y sigue siendo un sistema aleatorio.
A ver si tenemos cuidado, no es 1 de cada 27 sino 1 de cada 6^3...es decir, 1 de cada 216....notese la diferencia :)


Volviendo al tema, creo que tu mayor problema venia del % de tus formulas. Tambien para el srand, yo el time no se como trabajara, yo siempre utilice el getmilliseconds.

Saludos :)

Zaelsius

arc4random (stdlib.h) es "más aleatorio" que rand, y además no hace falta inicializar la semilla.

prospekt

Cita de: shephiroth en 27 de Mayo de 2011, 01:18:33 AM

Cita de: Hechelion en 12 de Mayo de 2011, 11:13:22 AMSi tiramos 3 dados, y en las 3 tiradas sale un 6 es un comportamiento completamente posible (1 de 27 ocasiones saldrá). y sigue siendo un sistema aleatorio.
A ver si tenemos cuidado, no es 1 de cada 27 sino 1 de cada 6^3...es decir, 1 de cada 216....notese la diferencia :)


Metiendome de lleno en el offtopic, si no me equivoco 6^3 sería una permutación con repetición y aquí hablamos de una combinación con repetición. A mi salen 56 posibles combinaciones, aunque acabo de hacer los calculos malamente y es posible que lo haya hecho mal.
Twitter: @AIProspekt

Hechelion

Shephiroth está bien, es 1 sobre 6^3 = 216. Yo me he embolado y he hecho 3^3 = 27, pero mirad la hora del post y además yo vivo al otro lado del océano.

Efectivamente eso es con repetición. Si no tienes repetición y tenemos 3 tiradas, seria 6*5*4=120 combinaciones diferentes.

shephiroth

hmmm......menudo offtopic xDD

Combinacion de p posiciones con n numeros:
-Con repeticion: n^p
-Sin repeticion: n!/(n-p)!

prospekt

Cita de: shephiroth en 29 de Mayo de 2011, 08:33:22 AM
hmmm......menudo offtopic xDD

Combinacion de p posiciones con n numeros:
-Con repeticion: n^p
-Sin repeticion: n!/(n-p)!

¿Esas formulas no son de permutaciones? Según mis apuntes de discreta las combinaciones con repetición (es decir, obtener n elementos de un conjunto de m con repetición y sin que el orden importe, vamos, el resultado de una tirada de 3 dados...) es:

(m+n-1)! / (n!(m-1)!)
Twitter: @AIProspekt

shephiroth

Cita de: prospekt en 30 de Mayo de 2011, 12:46:12 AM
¿Esas formulas no son de permutaciones? Según mis apuntes de discreta las combinaciones con repetición (es decir, obtener n elementos de un conjunto de m con repetición y sin que el orden importe, vamos, el resultado de una tirada de 3 dados...) es:

(m+n-1)! / (n!(m-1)!)

Hmmm......hay algo en esa formula que no me gusta, aunque no se que es. Si la aplicamos a la tirada de dados, n=3, m=6, luego (6+3-1)! / (3!(6-1! = 8! / 3!5! = 8*7*6/3*2 =8*7=56. Ahora bien, solo hay 56 combinaciones posibles?

Warchief

Combinatoria y probabilistica son dos cosas distintas.

- - Combinatoria

Cuando tiras 3 dados a la vez, el numero de combinaciones distintas es 56.
Son combinaciones con repeticion de m=6 elementos tomados de n=3 en 3 son:
(m+n-1)! / (n!(m-1)!) = 8! / (3! 5!) = 56
Donde, por ejemplo, 611 es la misma que 116, puesto que los has tirado a la vez y no sabes cual es cual.

Sin embargo, si los tiras en orden, 611 no es lo mismo que 116.
En este caso son Variaciones con repeticion de m=6 elementos tomados de n=3 en 3:
m^n = 6^3 = 216

En ningun caso son permutaciones porque no salen todos los numeros del dado. Para que pueda haber permutaciones, n tiene que ser mayor o igual a m.

- - Probabilistica

La pregunta es: Si tiramos 3 dados, cual es la probabilidad de que salgan todos 6?
Probabilidad = prob6en1 * prob6en2 * prob6en3 = 1/6 * 1/6 * 1/6  = 1 / 216
= numero de casos correctos / numero de casos posibles.

El truco es que algunas combinaciones de las 56 son mas probables que otras.

- - Para simplificar pensad en tirar 2 monedas = 2 elementos de 2 en 2

Combinaciones con repeticion = 3! / 2! = 3
= DosCaras, CarayCruz, DosCruces

Variaciones con repecition = 2^2 = 4
= DosCaras, CarayCruz, CruzyCara, DosCruces

La probabilidad de que salgan dos cruces es 1 entre 4, a pesar de que hay 3 combinaciones, porque 1 combinacion es mas probable que las otras dos.

Hechelion

Cita de: Warchief en 04 de Junio de 2011, 01:26:44 AM

En ningun caso son permutaciones porque no salen todos los numeros del dado. Para que pueda haber permutaciones, n tiene que ser mayor o igual a m.


Disculpa que sea tan majadero, pero te voy a pedir una fuente para esa definición. Por lo que yo recuerdo de mis libros de estadística (Combinatoria y permutaciones aparecen ahí) y lo que acabo de googlear (por las dudas) no existe ninguna definición que te obligue a que n deba ser mayor o igual a m para que sean permutaciones. Eso, o estamos dando un contexto completamente diferente al tema.

La definición que yo recuerdo es que permutación es todo posible ordenación de un conjunto dado.

Warchief

Hay varios ejemplos en internet.
http://www.aulafacil.com/CursoEstadistica/Lecc-18-est.htm
http://www.vitutor.com/pro/1/a_r.html
http://www.kalipedia.com/matematicas-estadistica/tema/combinatoria/variaciones-permutaciones-combinaciones.html?x=20070926klpmateyp_61.Kes

Aunque también he visto gente que usa el término permutación para lo que yo he llamado variación.

Como bien dices, permutación es toda posible ordenación de un conjunto dado. Es decir, que todos los elementos del grupo original están en el conjunto, y lo único que varía es el orden. Por eso n tiene que ser igual o mayor a m. En el caso de los dados tenemos 6 valores en el conjunto original, pero los tomamos de 3 en 3, por lo que aparte del orden, también varían los elementos que escogemos. Esa es la diferencia entre variación y permutación.

En general se suele decir que la permutación es un caso específico de variación, donde M=N, por lo que
Fórmula general de Variaciones de M elementos tomandos de N en N:
VAR(m,n) = m! / (m-n)!
Si consideramos las permutaciones como variaciones donde M = N, queda:
PER(m) = VAR(m,m) = m! / 0! = m!, que es la fórmula de las permutaciones.

Si N es mayor que M, entonces hay repetición.

- - -
En el caso de los dados, las permutaciones se pueden usar para hallar los casos correctos. Ejemplos:

¿Qué probabilidad hay de que salgan 3 seises?
Casos favorables / casos posibles = PR(3,3) / VR(6,3) = (3!) / 3!) / (6^3) = 216
PR(3,3) Son permutaciones con repeticion de 3 elementos en los que el primero se repite 3 veces (todos son seis)

¿Qué probabilidad hay de que salgan un 3, un 4 y un 5?
Casos favorables / casos posibles = P(3) / VR(6,3) = 3! / (6^3) = 6 / 216

¿Qué probabilidad hay de que salgan dos 1, y un 6?
Casos favorables / casos posibles = PR(3;2,1) / VR(6,3) = (3! / ( 2!*1!) ) / (6^3) = 3 / 216

He aquí lo que comenté de que de las 56 combinaciones, hay algunas más probables. Esto es así porque al estar formadas por números distintos, tienen más permutaciones que las combinaciones que repiten números. Si sumamos las permutaciones de cada una de las 56 combinaciones, obtenemos las 216 variaciones.






Stratos es un servicio gratuito, cuyos costes se cubren en parte con la publicidad.
Por favor, desactiva el bloqueador de anuncios en esta web para ayudar a que siga adelante.
Muchísimas gracias.