Programadores => General Programadores => Mensaje iniciado por: Altair en 12 de Mayo de 2011, 09:24:37 am

Título: Numeros aleatorios
Publicado por: Altair en 12 de Mayo de 2011, 09:24:37 am
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.
Título: Re: Numeros aleatorios
Publicado por: Hechelion en 12 de Mayo de 2011, 11:13:22 am
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.
Título: Re: Numeros aleatorios
Publicado por: Phoer en 12 de Mayo de 2011, 05:20:45 pm
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 ;)
Título: Re: Numeros aleatorios
Publicado por: Vicente en 12 de Mayo de 2011, 06:32:27 pm
No estaras llamando a srand(time(NULL)); varias veces no?
Título: Re: Numeros aleatorios
Publicado por: Phoer en 12 de Mayo de 2011, 07:54:06 pm
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
Título: Re: Numeros aleatorios
Publicado por: shephiroth en 27 de Mayo de 2011, 01:18:33 am
Buenas.

Primero, respecto a las formulas
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;
- 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 %

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.
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 :)
Título: Re: Numeros aleatorios
Publicado por: Zaelsius en 27 de Mayo de 2011, 03:27:15 am
arc4random (stdlib.h) es "más aleatorio" que rand, y además no hace falta inicializar la semilla.
Título: Re: Numeros aleatorios
Publicado por: prospekt en 27 de Mayo de 2011, 02:30:30 pm

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.
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.
Título: Re: Numeros aleatorios
Publicado por: Hechelion en 27 de Mayo de 2011, 10:39:52 pm
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.
Título: Re: Numeros aleatorios
Publicado por: 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)!
Título: Re: Numeros aleatorios
Publicado por: prospekt en 30 de Mayo de 2011, 12:46:12 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)!)
Título: Re: Numeros aleatorios
Publicado por: shephiroth en 03 de Junio de 2011, 11:56:08 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?
Título: Re: Numeros aleatorios
Publicado por: Warchief en 04 de Junio de 2011, 01:26:44 am
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.
Título: Re: Numeros aleatorios
Publicado por: Hechelion en 04 de Junio de 2011, 07:47:00 pm

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.
Título: Re: Numeros aleatorios
Publicado por: Warchief en 05 de Junio de 2011, 01:29:31 am
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.
Título: Re: Numeros aleatorios
Publicado por: Warchief en 05 de Junio de 2011, 01:35:31 am
Si lo que no te cuadra es que N pueda ser mayor que M, es sólo una manera de decir que hay elementos repetidos.
Por ejemplo:
Dado el conjunto abc, se pueden hallar las permutaciones. P(3) = 3! = 6.
Es lo mismo que variaciones de 3 elementos tomados de 3 en 3. (M=N=3)

Dado el conjunto 116, se pueden hallar las permutaciones con repetición, donde el primer elemento aparece dos veces. PR(3;2,1) = 3! / (2!1!) = 3.
Es como decir que originalmente teníamos 2 elementos (1 y 6), tomados de 3 en 3, con repetición de uno de ellos (1). A eso me refiero con que N puede ser mayor que M (M=2; N=3). Sin embargo, en la fórmula N=3, no hay concepto de M=2. Los dos 1s son considerados elementos distintos para el total.
Título: Re: Numeros aleatorios
Publicado por: shephiroth en 05 de Junio de 2011, 03:54:51 pm
Efectivamente, este comentario esta errado.
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.

Como fuente la wikipedia (ironicamente, en el termino combinatoria xDD): http://es.wikipedia.org/wiki/Combinatoria

En los ejemplos de combinatoria numerica dice, cito:
Citar
Considérese el conjunto S = {A,E,I,O,U}. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.

Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).

    En este caso, ejemplos pueden ser IOU, AEI o EAI.

Saludos
Título: Re: Numeros aleatorios
Publicado por: Warchief en 05 de Junio de 2011, 09:35:33 pm
Esta imagen lo resume:
(http://1.bp.blogspot.com/_ECqTg43vZ-g/SoNF6ysYJ7I/AAAAAAAAABQ/IgLgYoCWjz4/s400/Dibujo.jpg)
(fuente http://estructurasdiscretas2-2009.blogspot.com/2009/08/tarea-2-formulas-de-variacion.html)

http://es.wikipedia.org/wiki/Permutaci%C3%B3n
En combinatoria:
A éste número se le llama permutaciones de n en k. Otras notaciones son *imagen*  o *imagen*  (en algunas partes del mundo se le conoce como variaciones y se denota *imagen* ).

Todos estos recursos distinguen entre variación y permutación, donde permutación es una variación con m=n.
http://es.answers.yahoo.com/question/index?qid=20110528210626AApYivH
http://www2.uca.es/matematicas/Docencia/ESI/1710003/Apuntes/Leccion4.pdf
http://www.unlu.edu.ar/~dcb/matemat/combina1.htm

Cualquiera de los recursos que se encuentran en google buscando "variacion permutacion" hace dicha distinción:
http://www.google.com/search?btnG=1&pws=0&q=variacion+permutacion

Si en vuestra región llaman N-permutación (que es la primera vez que lo veo) a las variaciones donde N != M, sin problema. La distinción importante es entre combinación y variación/permutación.
Título: Re: Numeros aleatorios
Publicado por: Warchief en 05 de Junio de 2011, 09:39:53 pm
Considérese el conjunto S = {A,E,I,O,U}. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.

Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).

En este caso, ejemplos pueden ser IOU, AEI o EAI.

Para mí eso no son N-permutaciones o permutaciones, son variaciones. Y la fórmula es V5,3 =5! / 2! = 60.

La parte anterior, que no has puesto, sí:
Citar
Un primer problema podría consistir en hallar el número de formas diferentes en que podemos sacar las tarjetas una después de otra (es decir, el número de permutaciones del conjunto).
Por ejemplo, dos formas distintas podrían ser: EIAOU o OUAIE.

P5 = 5! = 120

Pero no me quita el sueño un problema de notación.
Título: Re: Numeros aleatorios
Publicado por: prospekt en 06 de Junio de 2011, 12:01:42 am
Gracias por la aclaración, el cacao que llevaba en la cabeza era grande ya que entendía por permutaciones, variaciones y combinaciones cosas diferentes a las que estais diciendo.
Título: Re: Numeros aleatorios
Publicado por: Hechelion en 06 de Junio de 2011, 12:43:51 am
Considérese el conjunto S = {A,E,I,O,U}. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.

Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).

En este caso, ejemplos pueden ser IOU, AEI o EAI.

Para mí eso no son N-permutaciones o permutaciones, son variaciones. Y la fórmula es V5,3 =5! / 2! = 60.

La parte anterior, que no has puesto, sí:

Tal como dices, ahí está el problema, en mis libros, eso si se llama permutación, aunque en los tuyos, al parecer, les llaman variaciones.

Por universalidad, trataría de no expandir esa regla, pues en foros donde se reune gente de diferentes partes del mundo va a generar controversia ;)
Título: Re: Numeros aleatorios
Publicado por: Mars Attacks en 06 de Junio de 2011, 09:33:44 pm
Chinchetaaaaaaa
Título: Re: Numeros aleatorios
Publicado por: [EX3] en 06 de Junio de 2011, 11:34:59 pm
Chinchetaaaaaaa
Hecho :)

Salu2...
Título: Re: Numeros aleatorios
Publicado por: Mars Attacks en 07 de Junio de 2011, 09:22:06 pm
Graciaaaaaaaaaaaaaas :D
Título: Re: Numeros aleatorios
Publicado por: Gallo en 21 de Noviembre de 2011, 09:34:26 am
Y este niños, es el motivo por el cual no tenéis que ir a la Universidad  >:D, haced un grado superior y vuestra mente lo agradecerá.
Título: Re: Numeros aleatorios
Publicado por: Mars Attacks en 22 de Noviembre de 2011, 12:08:49 am
http://www.nature.com/nature/journal/v464/n7291/images/464988a-i1.0.jpg