在Python中按照近似比例分配项目
请看下面的更新...
我正在写一个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），而目标C、D和E则比较稀少（各1个）。
当目标数量是奇数时，最后一个prop_high目标会比其他目标少一个。随着目标数量接近玩家数量，每个prop_high目标会逐渐减少，直到最后，池中每个目标各有一个。
我下面做的就是给目标池的高端和低端分配数量，然后根据目标数量与玩家数量的接近程度来调整高端，减少一些值。这在8个玩家的情况下效果很好（目标池中的目标数量始终等于8），但就仅此而已。
我非常确定还有更好、更符合Python风格的方法来处理这种算法，而且我也觉得这是一种相对常见的设计模式。我只是不知道该从哪里开始搜索，以找到更优雅的处理这种结构的方法（而不是我现在使用的暴力方法）。
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
2 个回答
大约两年半前，我在这里问过一个问题，我觉得这个问题在这里也很相关。你可以这样使用：首先，列出每个目标的优先级。在你的例子中，目标池的前半部分（向下取整）优先级为3，后半部分优先级为1，一种实现方法是：
priorities = [3] * len(goals) / 2 + [1] * (len(goals) - len(goals) / 2)
当然，你可以用任何方式来创建你的优先级列表；不一定要是一半是3，一半是1。唯一的要求是所有的数值都必须是正数。
一旦你有了这个列表，就要把它归一化，使它的总和等于玩家的数量：
# Assuming num_players is already defined to be the number of players
normalized_priorities = [float(p) / sum(priorities) * num_players
for p in priorities]
然后应用我提到的算法之一，把这些浮点数四舍五入成代表实际分配的整数。在给出的答案中，只有两个算法能正确地进行四舍五入，并且满足最小方差的标准：调整后的分数分配（包括“更新”段落）和最小化舍入误差。方便的是，这两个算法似乎都适用于未排序的列表。以下是我用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]
在我所有的测试中，这两种方法是完全等效的，所以你可以选择其中任何一种来使用。
这里有一个使用示例：
>>> 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]
如果你想把额外的玩家分配给一组相同优先级的第一个目标，而不是最后一个，最简单的方法可能是在应用四舍五入算法之前和之后反转列表。
>>> def rlist(l):
... return list(reversed(l))
>>> rlist(minimal_roundoff_error(rlist(normalized_priorities)))
[6, 5, 2, 2, 2]
现在，这可能和你预期的分配不太一致，因为在我的问题中，我指定了一个“最小方差”的标准来判断结果。这可能不适合你的情况。你可以尝试“余数分配”算法，看看它是否对你更有效。
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
与其费力去计算比例，我选择一次分配一个目标，按照合适的比例来分配。在这里，'allocate_goals'这个生成器会先给每个低比例的目标分配一个目标，然后再给每个高比例的目标分配（这个过程会重复三次）。然后它会再重复这个过程。调用者在allocate中使用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)