最小分数の割り当て

Question

Eの要素数とSの数があるとします。

我々はそのようにセットに要素を割り当てる必要があり：

1. すべてがおおよそ同じ数の要素要素の
2. 数（最小と最大のセットの間のセット・サイズの最小 差）を含むセット可能な限り小さくする必要があります。
3. 各要素はに少なくともの合計のセットの最小％を割り当てる必要があります。この％は、（1）及び（2）問題の目的であり、そしていくつかの例ではトレードオフがあること

注意（これ が要素はもちろんであるが、複数のセットに応じ に割り当てられることを意味する）の各要素のために指定されていますそれらの間の。私は事実上、このトレードオフをパラメータ化する数学的な定式化/解法を探しています。一方、（3）は単なる問題の制約です。

どのように最適な割り当てを見つけるか？この問題は文献に名前がありますか？それが重要な場合は、具体的にはPythonで解決策を探しています。例として

---

、それらの各々は、分を指定して、我々は3セットおよび10個の要素を持っていると言います。セットの割合は次のとおりです。

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

出力：上記cycleで

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

は、ターゲット・セットにわたって無限に反復するために使用されます。 genは、確率に基づいて追加する要素の最小量を返しジェネレータである：最後

>>> 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)タプルを生成するために使用されます。