Zuweisungen mit minimalen Brüche

Question

Angenommen, wir haben eine Reihe von Elementen E und eine Reihe von Sets S.

Wir brauchen Elemente setzt, so dass zuzuweisen:

1. Alle in etwa die gleiche Anzahl von Elementen (Mindest Unterschied in Satzgröße zwischen dem kleinsten und dem größten Satz)
2. Die Anzahl der Elemente enthalten Sätze pro Satz sollte so klein wie möglich sein.
3. Jedes Element muss mindestens ein Minimum% der Sätze der Gesamtmenge zugewiesen werden. Diese% für jedes Element angegeben wird (diese bedeutet, dass Elemente sind natürlich entsprechend mehrere Sätze zugeordnet werden)

Beachten Sie, dass (1) und (2) sind Problem Ziele, und in einigen Fällen gibt es ein Nachteil ist, zwischen ihnen. Ich suche effektiv nach einer mathematischen Formulierung/Lösung, die diesen Kompromiss parameterisiert. Unterdessen (3) ist nur eine Problemeinschränkung.

Wie finden wir eine optimale Zuordnung? Hat dieses Problem einen Namen in der Literatur? Falls es darauf ankommt, suche ich speziell nach einer Lösung in Python.

---

Als Beispiel, sagen wir 3 Sätze und 10 Elemente haben, wobei jede von ihnen die min angibt. Fraktion von Sets wie folgt:

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

Man könnte einfach drehen stufenlos über die Sätze, um den nächsten Satz zu bestimmen, zuzuordnen. Dann für jedes Element berechnet, wie viele Sätze es zugewiesen werden soll, und dann tun, um die Zuordnung entsprechend:

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

Output:

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

In oben cycle verwendet wird unendlich über die Zielsätze iterieren. gen ist ein Generator, der die minimale Menge an Elementen kehrt auf den Wahrscheinlichkeiten hinzuzufügen basiert:

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

Schließlich zip verwendet wird (target set, element) Tupeln zu erzeugen, die dann in einer Schleife zugeordnet sind.