Asignar elementos según una relación aproximada en Python

Ver actualización a continuación …

Estoy escribiendo una simulación de Python que asigna un número arbitrario de jugadores imaginarios a un objective de un conjunto arbitrario de objectives. Los objectives tienen dos niveles o proporciones diferentes de escasez, prop_high y prop_low , en una proporción de aproximadamente 3: 1.

Por ejemplo, si hay 16 jugadores y 4 goles, o 8 jugadores y 4 goles, los dos grupos de goles se verían así:

 {'A': 6, 'B': 6, 'C': 2, 'D': 2} {'A': 3, 'B': 3, 'C': 1, 'D': 1} 

… con los objectives A y B ocurriendo 3 veces más a menudo que C y D. 6 + 6 + 2 + 2 = 16, que corresponde al número de jugadores en la simulación, lo cual es bueno.

Quiero tener un grupo de goles igual al número de jugadores y distribuidos de modo que haya aproximadamente tres veces más goles prop_low objectives prop_low .

¿Cuál es la mejor manera de construir un algoritmo de asignación de acuerdo con una proporción aproximada o aproximada, algo que pueda manejar el redondeo?

Actualizar:

Suponiendo que hay 8 jugadores, así es como esperamos que se vean las distribuciones de 2 a 8 goles (los jugadores prop_high están destacados):

  ABCDEFGH 2 6* 2 3 6* 1 1 4 3* 3* 1 1 5 3* 2* 1 1 1 6 2* 2* 1* 1 1 1 7 2* 1* 1* 1 1 1 1 8 1* 1* 1* 1* 1 1 1 1 

Estos números no corresponden a los jugadores. Por ejemplo, con 5 objectives y 8 jugadores, los objectives A y B tienen una alta proporción en el grupo (3 y 2 respectivamente), mientras que los objectives C, D y E son más raros (1 cada uno).

Cuando hay un número impar de goles, el último de prop_high obtiene uno menos que los otros. A medida que el número de goles se acerca al número de jugadores, cada uno de los objetos prop_high obtiene uno menos hasta el final, cuando hay uno de cada gol en el grupo.

Lo que he hecho a continuación es asignar cantidades a los extremos alto y bajo del grupo y luego hacer ajustes en el extremo alto, restando los valores de acuerdo a qué tan cerca está el número de goles al número de jugadores. Funciona bien con 8 jugadores (el número de goles en el grupo siempre es igual a 8), pero eso es todo.

Estoy absolutamente seguro de que hay una forma mejor y más Pythonic de manejar este tipo de algoritmo, y estoy bastante seguro de que es un patrón de diseño relativamente común. Simplemente no sé dónde empezar a buscar en Google para encontrar una forma más elegante de manejar este tipo de estructura (en lugar del método de fuerza bruta que estoy usando por ahora)

 import string import math letters = string.uppercase num_players = 8 num_goals = 5 ratio = (3, 1) prop_high = ratio[0] / float(sum(ratio)) / (float(num_goals)/2) prop_low = ratio[1] / float(sum(ratio)) / (float(num_goals)/2) if num_goals % 2 == 1: is_odd = True else: is_odd = False goals_high = [] goals_low = [] high = [] low = [] # Allocate the goals to the pool. Final result will be incorrect. count = 0 for i in range(num_goals): if count = overall_ratio: # Upper half of possible goals print offset for i in range(offset): index = -(int(i) + 1) high[index] -= 1 goals = goals_high + goals_low goals_quantities = high + low print "Players:", num_players print "Types of goals:", num_goals print "Total goals in pool:", sum(goals_quantities) print "High pool:", goals_high, high print "Low pool:", goals_low, low print goals, goals_quantities print "High proportion:", prop_high, " || Low proportion:", prop_low 

En lugar de tratar de obtener las fracciones correctas, solo asignaba los objectives uno a la vez en la proporción adecuada. Aquí, el generador de “allocate_goals” asigna un objective a cada uno de los objectives de baja proporción, luego a cada uno de los objectives de alta proporción (repitiendo 3 veces). Luego se repite. La persona que llama, al asignar, corta este generador infinito en el número requerido (el número de jugadores) usando itertools.islice.

 import collections import itertools import string def allocate_goals(prop_low, prop_high): prop_high3 = prop_high * 3 while True: for g in prop_low: yield g for g in prop_high3: yield g def allocate(goals, players): letters = string.ascii_uppercase[:goals] high_count = goals // 2 prop_high, prop_low = letters[:high_count], letters[high_count:] g = allocate_goals(prop_low, prop_high) return collections.Counter(itertools.islice(g, players)) for goals in xrange(2, 9): print goals, sorted(allocate(goals, 8).items()) 

Produce esta respuesta:

 2 [('A', 6), ('B', 2)] 3 [('A', 4), ('B', 2), ('C', 2)] 4 [('A', 3), ('B', 3), ('C', 1), ('D', 1)] 5 [('A', 3), ('B', 2), ('C', 1), ('D', 1), ('E', 1)] 6 [('A', 2), ('B', 2), ('C', 1), ('D', 1), ('E', 1), ('F', 1)] 7 [('A', 2), ('B', 1), ('C', 1), ('D', 1), ('E', 1), ('F', 1), ('G', 1)] 8 [('A', 1), ('B', 1), ('C', 1), ('D', 1), ('E', 1), ('F', 1), ('G', 1), ('H', 1)] 

Lo mejor de este enfoque (aparte de, creo, que es fácil de entender) es que se convierte rápidamente en una versión aleatoria.

Solo reemplaza allocate_goals con esto:

 def allocate_goals(prop_low, prop_high): all_goals = prop_low + prop_high * 3 while True: yield random.choice(all_goals) 

Hace algún tiempo (bueno, dos años y medio) hice una pregunta que creo que sería relevante aquí. Así es como creo que podría usar esto: primero, haga una lista de las prioridades asignadas a cada meta. En su ejemplo, donde la primera mitad del grupo de goles (redondeado hacia abajo) tiene prioridad 3 y el rest tiene prioridad 1, una forma de hacerlo es

 priorities = [3] * len(goals) / 2 + [1] * (len(goals) - len(goals) / 2) 

Por supuesto, puede crear su lista de prioridades de la forma que desee; no tiene que ser mitad 3s y mitad 1s. El único requisito es que todas las entradas sean números positivos.

Una vez que tenga la lista, normalícela para que tenga una sum igual al número de jugadores:

 # Assuming num_players is already defined to be the number of players normalized_priorities = [float(p) / sum(priorities) * num_players for p in priorities] 

Luego aplique uno de los algoritmos de mi pregunta para redondear estos números de punto flotante a enteros que representan las asignaciones reales. Entre las respuestas proporcionadas, solo hay dos algoritmos que hacen el redondeo correctamente y satisfacen el criterio de varianza mínima: distribución fraccional ajustada (incluido el párrafo “Actualizar”) y minimizando el error de redondeo . Convenientemente, ambos parecen funcionar para listas no ordenadas. Aquí están mis implementaciones de Python:

 import math, operator from heapq import nlargest from itertools import izip item1 = operator.itemgetter(1) def floor(f): return int(math.floor(f)) def frac(f): return math.modf(f)[0] def adjusted_fractional_distribution(fn_list): in_list = [floor(f) for f in fn_list] loss_list = [frac(f) for f in fn_list] fsum = math.fsum(loss_list) add_list = [0] * len(in_list) largest = nlargest(int(round(fsum)), enumerate(loss_list), key=lambda e: (e[1], e[0])) for i, loss in largest: add_list[i] = 1 return [i + a for i,a in izip(in_list, add_list)] def minimal_roundoff_error(fn_list): N = int(math.fsum(fn_list)) temp_list = [[floor(f), frac(f), i] for i, f in enumerate(fn_list)] temp_list.sort(key = item1) lower_sum = sum(floor(f) for f in fn_list) difference = N - lower_sum for i in xrange(len(temp_list) - difference, len(temp_list)): temp_list[i][0] += 1 temp_list.sort(key = item2) return [t[0] for t in temp_list] 

En todas mis pruebas, ambos métodos son exactamente equivalentes, por lo que puede elegir cualquiera de los dos para usar.


Aquí hay un ejemplo de uso:

 >>> goals = 'ABCDE' >>> num_players = 17 >>> priorities = [3,3,1,1,1] >>> normalized_priorities = [float(p) / sum(priorities) * num_players for p in priorities] [5.666666..., 5.666666..., 1.888888..., 1.888888..., 1.888888...] >>> minimal_roundoff_error(normalized_priorities) [5, 6, 2, 2, 2] 

Si desea asignar los jugadores adicionales a los primeros objectives dentro de un grupo de igual prioridad, en lugar de los últimos, probablemente la forma más fácil de hacerlo es revertir la lista antes y después de aplicar el algoritmo de redondeo.

 >>> def rlist(l): ... return list(reversed(l)) >>> rlist(minimal_roundoff_error(rlist(normalized_priorities))) [6, 5, 2, 2, 2] 

Ahora, esto puede no coincidir con las distribuciones que espera, porque en mi pregunta especifiqué un criterio de “varianza mínima” que usé para juzgar el resultado. Eso podría no ser apropiado para su caso. Puede probar el algoritmo de “distribución restante” en lugar de uno de los dos que mencioné anteriormente y ver si funciona mejor para usted.

 def remainder_distribution(fn_list): N = math.fsum(fn_list) rn_list = [int(round(f)) for f in fn_list] remainder = N - sum(rn_list) first = 0 last = len(fn_list) - 1 while remainder > 0 and last >= 0: if abs(rn_list[last] + 1 - fn_list[last]) < 1: rn_list[last] += 1 remainder -= 1 last -= 1 while remainder < 0 and first < len(rn_list): if abs(rn_list[first] - 1 - fn_list[first]) < 1: rn_list[first] -= 1 remainder += 1 first += 1 return rn_list