python - Python中按近似比例分配元素

Question

请参阅下面的更新...

我正在编写一个 Python 模拟，从任意目标池中为任意数量的假想玩家分配一个目标。目标有两个不同的稀缺性级别或比例，prop_high 和 prop_low，比例大约为 3:1。

例如，如果有 16 名球员和 4 个进球，或者 8 名球员和 4 个进球，则两个进球池将如下所示:

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

...目标 A 和 B 的出现频率是 C 和 D 的 3 倍。6+6+2+2 = 16，这对应于模拟中的玩家数量，这很好。

我想要一个与玩家数量相等的目标池，并且这样分布，使得 prop_high 目标的数量大约是 prop_low 目标的三倍。

根据粗略或近似比率构建分配算法的最佳方法是什么——可以处理舍入的方法？

更新:

假设有 8 名球员，以下是 2 到 8 个进球的分布情况(prop_high 球员已加星号):

    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

这些数字与玩家无关。例如，有 5 个目标和 8 个球员，目标 A 和 B 在池中的比例较高(分别为 3 个和 2 个)，而 objective-c 、D 和 E 则较少(各有 1 个)。

当目标数量为奇数时，prop_high 中的最后一个比其他目标少一个。随着目标数量接近玩家数量，每个 prop_high 项都会减少一个，直到最后，池中每个目标都有一个。

我在下面所做的是为池的高端和低端分配数量，然后对高端进行调整，根据目标数量与玩家数量的接近程度减去值。它适用于 8 个玩家(池中的目标数始终等于 8)，但仅此而已。

我绝对确定有更好、更 Pythonic 的方法来处理这种算法，而且我非常确定这是一种相对常见的设计模式。我只是不知道从哪里开始谷歌搜索以找到一种更优雅的方式来处理这种结构(而不​​是我现在使用的蛮力方法)

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

我不会尝试正确分配分数，而是按适当的比例一次分配一个目标。这里“allocate_goals”生成器为每个低比率目标分配一个目标，然后为每个高比率目标分配一个目标(重复 3 次)。然后重复。调用者在分配中使用 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())

它产生这个答案:

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

这种方法的优点(除了我认为它易于理解之外)是它可以快速将其转换为随机版本。

只需将 allocate_goals 替换为:

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