(Python) algoritmo para seleccionar aleatoriamente una clave en función de la proporcionalidad / peso

Estoy un poco perdido en cuanto a cómo encontrar un algoritmo limpio para hacer lo siguiente:

Supongamos que tengo un dict k

>>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81} 

Ahora quiero seleccionar aleatoriamente una de estas claves, en función del “peso” que tienen en la cantidad total (es decir, la sum) de claves.

 >>> sum(k.values()) >>> 274 

Para que haya una

 >>> 68.0/274.0 >>> 0.24817518248175183 

24.81% de cambio porcentual que A es seleccionado.

¿Cómo escribirías un algoritmo que se ocupe de esto? En otras palabras, eso asegura que en 10.000 selecciones aleatorias, ¿A será seleccionado 2.481 veces?

Aquí hay una función de elección ponderada, con algún código que la ejerce.

 import random def WeightedPick(d): r = random.uniform(0, sum(d.itervalues())) s = 0.0 for k, w in d.iteritems(): s += w if r < s: return k return k def Test(): k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81} results = {} for x in xrange(10000): p = WeightedPick(k) results[p] = results.get(p, 0) + 1 print results Test() 

Esto debería funcionar:

 >>> k = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81} >>> import random >>> def weighted_pick(dic): ... total = sum(dic.itervalues()) ... pick = random.randint(0, total-1) ... tmp = 0 ... for key, weight in dic.iteritems(): ... tmp += weight ... if pick < tmp: ... return key 

El algoritmo sería este …

Seleccione un número al azar entre 1 y 274. Para hacerlo, llame a una función rand () (suponga que devuelve un valor entre 0 y 1), multiplique rand () por 274. El valor resultante ahora debe estar en un rango. Si está entre 1 y 68, seleccione A, si está entre 69 y 130, seleccione B y así sucesivamente. De esta manera, su probabilidad permanece viva y su operación tiene éxito.

PD: soy un chico de Java, no sé la syntax de Python.

La forma más sencilla de hacer esto cuando sus pesos son enteros relativamente pequeños (como en su ejemplo) es construir una cadena larga que contenga todos los caracteres en los pesos apropiados y elegir un carácter al azar:

 import random d = {'A': 68, 'B': 62, 'C': 47, 'D': 16, 'E': 81} s = ''.join(k*v for k,v in d.items()) random.choice(s) 

Tenga en cuenta que este método utilizará bastante memoria si sus pesos son grandes, en cuyo caso puede preferir una solución diferente.

También hay que mirar este enlace.

yk dos listas para k, di xk y yk

 from scipy import stats custm = stats.rv_discrete(name='test', values=(xk, yk)) custm.rvs(size=1) 

He desarrollado un algoritmo hace unos años, con la aplicación en Perl y SQL, puedes leer sobre él aquí , completo con análisis y pruebas de por qué (lo más probable) es correcto.

El concepto es simple: para cada elemento, seleccione un número aleatorio, hágalo pasar por alguna función que dependa del peso de los elementos y elija el elemento con el valor más bajo.

Esa función es:

 x[i] = -log(1 - rand())/weight[i]