Der beste Algorithmus zum Verteilen von n Elementen an x ​​Gruppen

Question

Was ist der beste Weg, n Elemente (sagen wir 2 bis 100) in x-Gruppen zu verteilen. Jede Gruppe sollte ungefähr die gleiche Menge an Gegenständen enthalten.

Leicht Beispiel n=100; x=2;

100/2 = 50 Stück pro Gruppe

Was passiert, wenn wir haben Gleitkommazahlen beteiligt, wie n=100; x=3;

100/3 wäre = 33,33

Wir bräuchten zwei Gruppen nisten 33 Elemente und eine Gruppe Verschachtelung 34.
Ein weiteres Beispiel: n=8; x=3

8/3 = 2,66

Vorschläge, wie dies in Angriff zu nehmen?

Nicht das es wichtig ist, aber nur für neugierige Köpfe, die Usecase: In meiner UI ich versuche, Tabstripes in mehrere Zeilen zu teilen, nur eine Zeile zu einer Zeit, so dass alle Tabstripes passen nicht in eine Zeile können wir sie programmatisch verteilen.

Wir freuen uns auf Ihre Antworten!

Answer 1

Nach dem Verteilen floor(n/x) Elemente über x Gruppen bleiben Sie mit n mod x = n - floor(n/x) * x Elemente, das ist ein Wert in [0, x). Sie können einfach 1 zu jeder Gruppe i=1..x mit i <= n mod x hinzufügen.

for i=1..x 
    group[i] <- floor(n/x) + (i <= n mod x ? 1 : 0) 

dies das gleiche wie

ist

for i=1..(n mod x) 
    group[i] <- ceil(n/x) 
for i=(n mod x + 1)..x 
    group[i] <- floor(n/x) 

Z.B. n = 11, x = 3 Sie am Ende folgenden haben:

group[1] <- 3 + (1 <= 2 ? 1 : 0) = 4 
group[2] <- 3 + (2 <= 2 ? 1 : 0) = 4 
group[3] <- 3 + (3 <= 2 ? 1 : 0) = 3 

Answer 2

Unter der Annahme, dass Ihre Gruppen in irgendeiner Form von Arrays von 0 mit ‚Groupcount‘ Gruppen, eine einfache Verteilung „von Reihen“ wäre indiziert sind so etwas wie:

g = 0 
for each element e 
    allocate e to group groups[g] 
    g++ 
    g = (g % groupCount) 

Wenn die Zuordnung zu einem Element zu einem Zeitpunkt zu langsam ist, kann die Zuordnung "nach Spalten" beschleunigt werden. Unter der Annahme, dass die restingElements und restingGroups der Zähler entsprechend initialisiert werden, würde es wie folgt aussehen:

for each group g 
    size = floor(remainingElements/remainingGroups) 
    allocate size elements to group g 
    remainingElements = remainingElements - size 
    --remainingGroups