Répartir les éléments selon un ratio approximatif en Python

Question

Voir la mise à jour ci-dessous...

J'écris une simulation Python qui attribue à un nombre arbitraire de joueurs imaginaires un but parmi un ensemble arbitraire de buts. Les objectifs ont deux niveaux ou proportions différents de rareté, prop_high et prop_low dans un rapport d'environ 3:1.

Par exemple, s'il y a 16 joueurs et 4 buts, ou 8 joueurs et 4 buts, les deux pools de buts ressembleront à ceci :

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

...avec des buts A et B survenant 3 fois plus souvent que C et D. 6+6+2+2 = 16, ce qui correspond au nombre de joueurs dans la simulation, ce qui est bien.

Je veux avoir une réserve de buts égale au nombre de joueurs et répartie de manière à ce qu'il y ait environ trois fois plus de buts. prop_high comme il y a prop_low objectifs.

Quelle est la meilleure façon de construire un algorithme d'allocation en fonction d'un ratio approximatif ou approximatif - quelque chose qui peut gérer les arrondis ?

Mise à jour :

En supposant 8 joueurs, voici à quoi devraient ressembler les distributions de 2 à 8 buts ( prop_high les joueurs sont marqués d'une étoile) :

    A   B   C   D   E   F   G   H
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

Ces chiffres ne correspondent pas à des joueurs. Par exemple, avec 5 buts et 8 joueurs, les buts A et B ont une forte proportion dans la poule (3 et 2 respectivement) tandis que les buts C, D et E sont plus rares (1 chacun).

Quand il y a un nombre impair de buts, le dernier des prop_high en reçoit un de moins que les autres. Au fur et à mesure que le nombre de buts se rapproche du nombre de joueurs, chacun des prop_high Les postes en obtiennent un de moins jusqu'à la fin, lorsqu'il ne reste plus qu'un seul de chaque objectif dans la poule.

Ce que j'ai fait ci-dessous est d'attribuer des quantités aux extrémités haute et basse de la poule, puis d'ajuster l'extrémité haute, en soustrayant des valeurs en fonction de la proximité entre le nombre de buts et le nombre de joueurs. Cela fonctionne bien avec 8 joueurs (le nombre de buts dans le pool est toujours égal à 8), mais c'est tout.

Je suis absolument sûr qu'il existe une meilleure façon, plus pythonique, de gérer ce genre d'algorithme, et je suis pratiquement sûr que c'est un modèle de conception relativement commun. Je ne sais pas par où commencer pour trouver une manière plus élégante de gérer ce type de structure (au lieu de la méthode de force brute que j'utilise pour l'instant).

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 < num_goals/2:         # High proportion
        high.append(math.ceil(prop_high * num_players))
        goals_high.append(letters[i])
    else:                           # Low proportion
        low.append(math.ceil(prop_low * num_players))
        goals_low.append(letters[i])
    count += 1

# Make adjustments to the pool allocations to account for rounding and odd numbers
ratio_high_total = len(high)/float(num_players)
overall_ratio = ratio[1]/float(sum(ratio))
marker = (num_players / 2) + 1
offset = num_goals - marker

if num_players == num_goals:
    for i in high:
        high[int(i)] -= 1
elif num_goals == 1:
    low[0] = num_players
elif ratio_high_total == overall_ratio and is_odd:
    high[-1] -= 1
elif ratio_high_total >= 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

Answer 1

Il y a quelque temps (ok, deux ans et demi) j'ai demandé une question que je pense être pertinente ici. Voici comment je pense que vous pourriez l'utiliser : tout d'abord, établissez une liste des priorités attribuées à chaque objectif. Dans votre exemple, où la première moitié de la réserve d'objectifs (arrondie à l'inférieur) obtient la priorité 3 et le reste la priorité 1, une façon de procéder est la suivante

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

Bien entendu, vous pouvez créer votre liste de priorités comme vous le souhaitez ; elle ne doit pas nécessairement être composée pour moitié de 3 et pour moitié de 1. La seule exigence est que toutes les entrées soient des nombres positifs.

Une fois que vous avez la liste, normalisez-la pour avoir une somme égale au nombre de joueurs :

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

Appliquez ensuite l'un des algorithmes de ma question pour arrondir ces nombres à virgule flottante en nombres entiers représentant les allocations réelles. Parmi les réponses données, il n'y a que deux algorithmes qui font l'arrondi correctement y satisfont au critère de variance minimale : distribution fractionnée ajustée (y compris le paragraphe "Mise à jour") et minimiser l'erreur d'arrondi . De manière pratique, les deux semblent fonctionner pour les listes non triées. Voici mes implémentations 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]

Dans tous mes tests, ces deux méthodes sont exactement équivalentes, vous pouvez donc choisir l'une ou l'autre.

---

Voici un exemple d'utilisation :

>>> 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 vous souhaitez attribuer les joueurs supplémentaires aux premiers buts d'un groupe de priorité égale, plutôt qu'aux derniers, le moyen le plus simple d'y parvenir est probablement d'inverser la liste avant et après l'application de l'algorithme d'arrondi.

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

Maintenant, il se peut que cela ne corresponde pas tout à fait aux distributions que vous attendez, car dans ma question, j'ai spécifié un critère de "variance minimale" que j'ai utilisé pour juger le résultat. Cela pourrait ne pas être approprié dans votre cas. Vous pourriez essayer le Algorithme de "distribution du reste". au lieu de l'un des deux que j'ai mentionnés ci-dessus et voyez si cela fonctionne mieux pour vous.

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

Answer 2

Plutôt que d'essayer d'obtenir des fractions correctes, j'attribuerais simplement les objectifs un par un dans le rapport approprié. Ici, le générateur 'allocate_goals' attribue un objectif à chacun des objectifs à faible ratio, puis à chacun des objectifs à ratio élevé (répété 3 fois). Puis il répète. L'appelant, dans allocate, coupe ce générateur infini au nombre requis (le nombre de joueurs) en utilisant 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())

Il produit cette réponse :

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)]

L'avantage de cette approche (outre, je pense, sa facilité de compréhension) est qu'il est rapide de la transformer en une version randomisée.

Remplacez simplement allocate_goals par ceci :

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