最小分数的作业

Question

假设我们有多个元素 E 和多个集合 S。

我们需要将元素分配给集合，以便：

所有集合大致包含相同数量的元素（最少最小和最大集合之间集合大小的差异）
每组的元素数越少越好。
每个元素需要分配到至少至少 % 的集合总数。这个 % 是为每个元素指定的（这个意味着元素当然被分配给多个集合因此）

请注意，(1) 和 (2) 是问题目标，在某些情况下，它们之间存在权衡。我正在有效地寻找一种参数化这种权衡的数学公式/解决方案。同时（3）只是一个问题约束。

我们如何找到最佳分配？这个问题在文献中有名字吗？以防万一，我专门在 Python.

中寻找解决方案

举个例子，假设我们有 3 个集合和 10 个元素，每个元素指定 min. 个集合的分数，如下所示：

0     97.844356
1     48.006223
2     99.772135
3     16.899074
4      0.111023
5      1.028894
6      5.315590
7    100.000000
8     99.838698
9     93.323315

Answer 1

您可以在这些集合上无限旋转以确定要分配给的下一个集合。然后为每个元素计算应该分配给多少组，然后相应地进行分配：

from itertools import cycle
from math import ceil

elems = [
    [0, 97.844356],
    [1, 48.006223],
    [2, 99.772135],
    [3, 16.899074],
    [4, 0.111023],
    [5, 1.028894],
    [6, 5.315590],
    [7, 100.000000],
    [8, 99.838698],
    [9, 93.323315]
]

def assign(elements, n):
    sets = [[] for _ in range(n)]
    gen = (e for e, p in elements for _ in range(ceil(p*n/100)))

    for s, e in zip(cycle(sets), gen):
        s.append(e)

    return sets

print(assign(elems, 3))

输出：

[[0, 1, 2, 4, 7, 8, 9], [0, 1, 2, 5, 7, 8, 9], [0, 2, 3, 6, 7, 8, 9]]

在上面 cycle 用于无限迭代目标集。 gen 是一个生成器，returns 根据概率添加的元素的最小数量：

>>> n = 3
>>> gen = (e for e, p in elems for _ in range(ceil(p*n/100)))
>>> list(gen)
[0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]

最后 zip 用于生成 (target set, element) 元组，然后在循环中分配这些元组。

最小分数的作业

Assignments with minimum fractions

python

math

mathematical-optimization

combinatorics

scipy