Blogia
Las Pequeñas Paranoyas de Motagirl

Aleatoriedad con probabilidades

- Tech/Geek/Craft
Aleatoriedad con probabilidades

(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

9 comentarios

juanfra -

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

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.

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.

motagirl2 -

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

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 .

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)

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 .

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...

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.