Skip to content

Instantly share code, notes, and snippets.

@jneira
Last active Dec 18, 2015
Embed
What would you like to do?
tenemos una lista ordenada (por :priority) de objetos. debe poder accederse por índice (lo que al menos en clj, descarta la posibilidad de usar un set).
puede haber múltiples objetos con el mismo valor :priority.
[{:priority 1} {:priority 1} {:priority 3} {:priority 3} {:priority 3} {:priority 5} {:priority 5} {:priority 8} {:priority 8} {:priority 8}]
en mi dominio, cada objeto tiene más claves aparte de :priority, pero son irrelevantes en este problema.
lo que deseamos es un método que nos dé el índice de acceso de un elemento al azar, un azar influido por las prioridades.
digamos que dos objetos con la misma :priority tienen elegibilidad equiprobable,
y uno con valor 2 debería tener la mitad de probabilidades de ser elegido que un objeto con prioridad 1,
uno con valor 3, un tercio que uno de 1... (no sé cómo enunciar esta relación elegantemente)
(ns prior)
(def ex [{:p 1} {:p 1} {:p 3} {:p 3} {:p 3}
{:p 5} {:p 5} {:p 8} {:p 8} {:p 8}])
(defn max-prob [xs]
(/ 1 (apply + (map #(/ 1 (:p %)) xs))))
(defn rnd-idx [xs]
(let [mp (max-prob xs)]
(loop [r (rand) i 0
[{p :p} & t] xs]
(let [ap (- r (/ mp p))]
(if (<= ap 0) i
(recur ap (inc i) t))))))
var ex=[{p:1},{p:1},{p:3},{p:3},{p:3},
{p:5},{p:5},{p:8},{p:8},{p:8}]
function maxProb (xs) {
var acc=0
for (v of xs) acc+=1/v.p
return 1/acc
}
function rndIdx (xs) {
var mp=maxProb(xs)
var r=Math.random()
for (i in xs) {
r-=mp/xs[i].p
if (r<=0) return i
}
return i
}
@vstarck
Copy link

vstarck commented Jun 11, 2013

Originalmente habia pensado algo como lo de Venky, lo confieso :<

Multiplicar la cantidad de apariciones en la lista de cada elemento por la prioridad y tomar uno al azar. El inverso cambio los planes :p

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment