Facebook Twitter Google +1     Admin





Who the Hell...?!

motagirl2, la culpable de todo esto

¿De qué va esto?

Temas



¿Más cosas interesantes?

Elementos compartidos de motagirl2


Google



Quiero estar al dia!

- Subscribirme usando mi agregador de noticias ^^
- No, gracias, prefiero recibir un mail cuando haya nuevos artículos ;)

¿Dónde está mota?


En Anobii
En DeviantArt
En Facebook
En Flickr
En Instagram
En LastFM
En Lomography
En Tumblr
En Twitter
En YouTube


Aleatoriedad con probabilidades

20140404185445-dice.jpg

(Iba a publicar esto en Facebook, pero al final he pensado que ya que tengo un blog medio muerto, lo mínimo es desvariar un poco en él de vez en cuando)

Me encontraba esta mañana en el proceso de maquillarme (porque ser developer no está reñido con tener unas pestañas de infarto) cuando por algún motivo me he preguntado si sería muy complicado hacer una aplicación (muy sencillita) que ordenara listas aleatoriamente, pero teniendo en cuenta que algunos elementos de la lista tuviesen una prioridad más alta o más baja. Es decir, que fuera más probable que algunos elementos (con prioridad más alta) estuviesen más arriba en la lista, pero que eso no impidiera que otros elementos con menor prioridad estuviesen delante de ellos (aunque esto debería ser menos probable)

Así de primeras, lo que me ha venido a la cabeza es generar para cada elemento de la lista un número aleatorio (en el intervalo  (0, 1], por ejemplo), y multiplicar por un coeficiente relaccionado con la prioridad (simplificando, pongamos 0.5: prioridad normal y 1: prioridad alta). Luego se ordenaría la lista en función del número resultante, de mayor a menor. En principio como el peso de los elementos de menor prioridad se reduce a la mitad (porque su coeficiente era 0.5) lo normal sería que estuviesen más abajo en la lista que los elementos de prioridad alta (que no varían, al multiplicar por 1). Ojo, sería lo normal, pero no sería imposible, como he dicho antes, que hubiese elementos de prioridad menor por encima de los de prioridad alta (nada impediría que un elemento de prioridad baja tenga un peso inicial de -por ejemplo- 0.8 que se convierte en 0.4 al final, y otro elemento de prioridad alta con peso de 0.35 -y este estaría por abajo en la lista al final-)

Sí, lo sé, es muy cutre. Otra posibilidad sería multiplicar dos veces por un número aleatorio (0, 1] a los elementos de menor prioridad (siempre se reducirían aunque no sabríamos cuánto). O (esta opción parece más elegante) utilizar distintas distribuciones normales con distintas funciones de densidad (y aparentemente esto existe en C++)

Soltada toda esta fumada mental, la pregunta es ¿a alguien se le ocurre algo mejor? Ahí debajo teneis los comentarios :D

Perpetrado por MotaGirl
04/04/2014 18:55 # id #. Tech/Geek/Craft

Comentarios » Ir a formulario



gravatar.comPerpetrado por Miki

Si he entendido bien lo quieres, se debería impedir que los de alta prioridad estuvieran abajo en la lista, pero se debería permitir a algunos de baja prioridad estar arriba en la lista.
Lo primero que se me ocurre es limitar el rango de aletoriedad. Así, los de alta prioridad podrían ser aleatorios entre 0.4 y 1.0, y los de baja prioridad entre 0.0 y 0.6.
Otra forma que se me ocurre es, tras obtener el valor aleatorio, aplicar un offset de +0.3 o -0.3, según la prioridad. Claro, esto puede dar resultados por encima de 1.0 y por debajo de 0.0, pero eso no importa, ¿no? Aunque me da la impresión de que este método no funcionará tan bien como el anterior.

Elegir la distribución aleatoria adecuada parece lo más correcto, pero estas cosas me dan mucha tirria y no se la deseo a nadie xD

Lo mejor que se me ocurre es que implementes un test para evaluar si una lista está "bien" ordenada (que cumpla los requisitos que quieres), y probar todos los algoritmos que has comentado y los que te sugieran con, por ejemplo, 1000 listas generadas con cada uno. Así podrás ver cuánto tiempo toman, cómo de bien se ordenan las listas... y te puedes quedar con el mejor.



¿Cuándo? 04/04/2014 21:27.


gravatar.comPerpetrado por motagirl2

Me gusta, me gusta lo de usar distintos rangos que se solapen "un poquito". Incluso con rangos (0, 0.8] para poco prioritarios y [0.7, 1] para prioritarios todavía puede parecerse más a lo que quiero...



¿Cuándo? 04/04/2014 22:01.


gravatar.comPerpetrado por juanfra

He encontrado dos ejemplos simples que lo mismo te sirven: este es simple pero no es eficiente para listas gigantes http://stackoverflow.com/a/12265980 y este mola un huevo http://stackoverflow.com/a/9260063 .



¿Cuándo? 04/04/2014 22:45.


gravatar.comPerpetrado por motagirl2

Buf, la primera es muy chusca juanfra!! jaja Y la segunda requiere BD. Meter una BD por medio ya sería un coñazo y un lío innecesario (no serán listas gigantes)



¿Cuándo? 04/04/2014 22:51.


gravatar.comPerpetrado por juanfra

Es que cuando veo un ejemplo que habla sobre distribuciones, recuerdo el instituto y me bloqueo XD . Se me ocurre otra forma que además es eficiente, pero no te lo digo que no te va a gustar XD .



¿Cuándo? 04/04/2014 23:51.


gravatar.comPerpetrado por motagirl2

Venga, me voy a arriesgar a preguntar... ¿Cuál es esa forma? :D



¿Cuándo? 05/04/2014 00:11.


gravatar.comPerpetrado por juanfra

Asignas un rango a cada elemento dependiendo del peso de cada uno. Por ejemplo:

Bob: 100
Alice: 90
Peter: 50

Bob tendría el rango del 0 a 99, Alice de 100 a 189 y Peter de 190 a 240. Generas un número aleatorio entre 0 y 240 y miras que elemento tiene ese número.

Pequeño, rápido y fácil de entender. Si miras el código después de un año no te vas a quedar con cara de idiota pensando qué leches hace el código, cosas que me da a mí que si pasará con todas las soluciones overenginered que estoy viendo :P .

No he mirado cómo programarlo, pero al menos en python debe ser sencillo.



¿Cuándo? 05/04/2014 00:43.


gravatar.comPerpetrado por motagirl2

Pero yo creo que eso no soluciona el problema, no veo donde está el "criterio de ordenación" ahí. Sí, vas a escoger un elemento con más probabilidad que otro, pero no es lo que quería.



¿Cuándo? 05/04/2014 00:47.


gravatar.comPerpetrado por juanfra

Se me había olvidado eso :P . Supongo que generando la lista mediante el random y descartando los elementos que ya están.



¿Cuándo? 05/04/2014 01:08.


Añadir un comentario



No será mostrado.





Artículos anteriores

Blog creado con Blogia. Esta web utiliza cookies para adaptarse a tus preferencias y analítica web.
Blogia apoya a la Fundación Josep Carreras.

Contrato Coloriuris