在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_low目标的三倍左右有prop_high目标。

如何构建一个分配算法，使其按照粗略或近似比率（可以处理四舍五入）？

更新：

假设有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

- Andrew

---

你能解释一下这个算法中的重要部分并且重述一下问题吗？如果我理解正确的话，你有一定数量的目标，少于或等于球员数量。从这些目标中，你希望为每个球员抽取一个目标，以使得球员之间的目标分配大致上有三倍的“prop_high”目标与“prop_low”目标？球员之间目标的排序是否重要？ - Cory Dolphin

抱歉，我会重新措辞。是的，我想要一个目标池，目标数量等于球员数量，并分配得到大约三倍于prop_low目标数量的prop_high目标。顺序并不重要；最终所有目标都将是随机的。 - Andrew

所有“高水平”的玩家是否必须分配相同数量的目标？那么“低水平”的玩家呢？如果比率仅在期望值上匹配，您是否满意？或者您是否要求每个分配尽可能接近所需比率？ - jrennie

我希望我刚才已经澄清了所有那些问题。我稍后会处理分配给玩家的实际任务...这个工作正常进行。我正在尝试建立可能目标的池，以便池中的总数等于玩家数量。玩家不是“高”或“低”...目标普遍性是“高”或“低”。 - Andrew

太棒了，优雅的回答。非常感谢！ - Andrew

Answer 1

一段时间以前（好吧，两年半前），我提出了一个问题，我认为这里会很相关。这是我认为您可以使用的方法：首先，建立一个列出每个目标分配的优先级的列表。在您的示例中，前一半的目标池（向下取整）获得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

- David Z

---

天哪，这太不可思议了！我刚玩了一下这些算法，似乎都能正常工作！明天早上我会继续尝试，确保一切都正常。谢谢！ - Andrew

Answer 2

不要试图精确计算比例，我只是将目标按照适当的比例一个一个地分配。这里的“allocate_goals”生成器为每个低比例目标分配一个目标，然后为每个高比例目标分配一个目标（重复3次）。然后再次重复。在“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)

- user97370