Einführung

Bei einer allgemeinen Wahl möchte man einen konstanten Preis pro Parlamentssitz berechnen. Dies bedeutet, dass wir für N >= 0die Verteilung der Sitze und eine Liste nsder Stimmen pro Partei eine dsolche Nummer finden möchten

sum(floor(n/d) for n in ns) == N 

Um die Dinge interessanter (und realer) zu machen, fügen wir zwei weitere Fakten hinzu:

1. Zwei Parteien können sich zu einer "Koalition" zusammenschließen, so dass die Sitze der "Koalition" durch die Summe der Stimmen aller Parteien in ihr zugeteilt werden. Dann werden die Sitze der 'Koalition' in ähnlicher Weise zwischen den Parteien aufgeteilt (Teiler finden usw.)

2. Eine Partei, die einen bestimmten Prozentsatz der Stimmen nicht erreicht hat (z. B. 3,25%), erhält automatisch 0 Sitze, und ihre Stimmen zählen nicht für eine „Koalition“.

Herausforderung

Sie erhalten:

1. Eine Liste von Listen, jede der verschachtelten Listen enthält ganze Zahlen (Anzahl der Stimmen) und hat die Länge 1 für eine einzelne Partei oder die Länge 2 für eine "Koalition".
2. Minimaler Prozentsatz der Stimmen (alias "Balken" für "Sperrfeuer"), um Sitze zu erhalten, als Bruchteil (3,25% werden als 0,0325 angegeben)
3. Gesamtzahl der auf alle Parteien zu verteilenden Sitze (Ganzzahl)

Sie müssen dieselbe verschachtelte Listenstruktur ausdrucken, wobei die Anzahl der Stimmen durch Parlamentssitze ersetzt wird.

Gewinner ist der Code mit der geringsten Anzahl von Bytes.

Ecke fällen:

• Es kann (und wird in der Regel auch) mehr als einen möglichen Teiler geben. Da es nicht in der Ausgabe enthalten ist, spielt es keine Rolle.
• Stellen Sie sich N=10und vor ns = [[1]], der Divisor darf also 0,1 sein (keine ganze Zahl)
• Einige Fälle können nicht gelöst werden, zum Beispiel ns=[[30],[30],[100]], bar=0, N=20. Es gibt eine Grenze, d=7.5an der die Summe der Floored-Werte von 19 auf 21 springt. Es wird nicht erwartet, dass Sie diese Fälle lösen. (Dank an Community-Mitglied Arnauld für den Hinweis auf diesen Fall)

Beispiel für Ein- und Ausgabe

Ein sehr nicht optimiertes Python3-Beispiel:

from math import floor

def main(_l, bar, N):
    # sum all votes to calculate bar in votes
    votes = sum(sum(_) for _ in _l)

    # nullify all parties that didn't pass the bar
    _l = [[__ if __ >= bar * votes else 0 for __ in _] for _ in _l]

    # find divisor for all parliament seats
    divisor = find_divisor([sum(_) for _ in _l], N)

    # find divisor for each 'coalition'
    divisors = [find_divisor(_, floor(sum(_)/divisor)) for _ in _l]

    # return final results
    return [[floor(___/_) for ___ in __] for _, __ in zip(divisors, _l)]

def find_divisor(_l, N, _min=0, _max=1):
    s = sum(floor(_ / _max) for _ in _l)
    if s == N:
            return _max
    elif s < N:
            return find_divisor(_l, N, _min, (_max + _min) / 2)
    else:
            return find_divisor(_l, N, _max, _max * 2)

print(main(l, bar, N))

Beispiel Eingabe:

l = [[190970, 156473], 
    [138598, 173004], 
    [143666, 193442], 
    [1140370, 159468], 
    [258275, 249049], 
    [624, 819], 
    [1125881], 
    [152756], 
    [118031], 
    [74701]]
bar = 0.0325
N = 120

Und seine Ausgabe:

[[6, 4], [0, 5], [4, 6], [35, 5], [8, 8], [0, 0], [35], [4], [0], [0]]

Einige weitere Beispielausgaben:

Wenn bar=0.1wir eine interessante Auseinandersetzung zwischen zwei Parteien bekommen, da keine der kleineren Parteien dazugezählt wird:

[[0, 0], [0, 0], [0, 0], [60, 0], [0, 0], [0, 0], [60], [0], [0], [0]]

Und wenn N=0(Eckfall) dann bekommt natürlich keiner was:

[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0], [0], [0], [0]]

05AB1E , 42 39 Bytes

ÐOOI*@*DO¸I¸¸2Fнζε`sDO/*Щ±/D{®1%Oòè‹+ï

Probieren Sie es online!

In 05AB1E fehlt eine gute Rekursion, daher wäre die Implementierung einer binären Suche wie im Referenzcode schmerzhaft. Zum Glück müssen wir den Teiler gar nicht finden!

Nehmen wir ein einfaches Beispiel: [600, 379, 12, 9] Stimmen, 100 Sitze, keine Koalitionen, keine Bar. Zuerst berechnen wir, wie viele Fraktionssitze jede Partei erhält, wobei Fraktionssitze als definiert werden party_votes * seats / sum_of_votes. In unserem Beispiel ergibt dies [60, 37,9, 1,2, 0,9].

Das Interessante daran ist, dass eine Partei, die nur einen fBruchteil der Sitze erhält, entweder einen int(f)oder einen int(f) + 1echten Sitz erhält . Dies bedeutet, dass wir bereits wissen, wie 60 + 37 + 1 = 98 der Sitze zugewiesen werden, und dass wir 2 „Bonussitze“ zur Verteilung auf die 4 Parteien übrig haben (keine Partei kann mehr als 1 Bonussitz erhalten). An wen gehen diese Bonussitze? Die Parteien mit der höchsten Quote von f / (int(f) + 1)(Nachweis als Übung dem Leser überlassen). In unseren Beispielen sind die Verhältnisse so [0.98, 0.997, 0.6, 0.9], dass die ersten beiden Parteien jeweils einen Bonussitz erhalten.

Werfen wir einen Blick auf den Code. Erstens ersetzen wir die Stimmenzahl aller Parteien, die die Messlatte nicht erreicht haben, durch 0:

Ð          # triplicate the first input (list of votes)
 OO        # flattened sum
   I*      # multiply by the second input (bar)
     @     # greater than? (returns 0 or 1)
      *    # multiply

Um die fehlende Rekursion zu umgehen 2F, wiederholen wir den Hauptcode zweimal mit einem Pseudonym . Beim ersten Durchgang werden die gesamten Sitze zwischen den Koalitionen aufgeteilt, und beim zweiten Durchgang werden die Sitze jeder Koalition zwischen ihren Parteien aufgeteilt. Da der erste Durchgang nur einmal ausgeführt wird, der zweite Durchgang jedoch für jede Koalition ausgeführt wird, ist dies mit ziemlich viel Arbeit verbunden.

DO¸I¸¸2Fнζε`s    # i don’t want to detail this tbh

Okay, nach diesem undurchsichtigen Teil ist die Spitze des Stapels nun eine Liste von Stimmen (Koalitionsstimmen im ersten Durchgang, Parteistimmen im zweiten Durchgang) und darunter die Anzahl der zuzuteilenden Sitze. Wir verwenden dies, um die Liste der Nachkommastellen zu berechnen:

D        # duplicate
 O       # sum  
  /      # divide each vote count by the sum
   *     # multiply by the number of seats
    ©    # save the fractional seats in variable r

Nun berechnen wir die Verhältnisse:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitweise klappt das nicht schön, hier. Es wird auf eine Ganzzahl gekürzt, 1 addiert und negiert, alles in einem einzigen Byte. Warum negieren? In 05AB1E gibt die Division durch 0 0 zurück, und diese müssen zuletzt sortiert werden.

D {# sortierte Kopie der Quoten ®1% # Bruchstimmen Mod 1 (auch als Dezimalzahl bezeichnet) O # Summe der oben genannten (dies ist die Anzahl der Bonussitze) ò # rund bis zum nächsten (erforderlich aufgrund von Gleitkomma bs) è # Index in die sortierten Verhältnisse

Dies ergibt das (n + 1) beste Verhältnis, wobei n die Anzahl der Bonusplätze ist (+1, da die Indexierung auf 0 basiert). Die Parteien, die einen Bonussitz erhalten, haben also ein Verhältnis, das strikt darunter liegt.

‹      # less than
 +     # add to the fractional seats
  ï    # truncate to integer

Python 2 , 220 Bytes

def d(l,n,a=0,b=1.):s=sum(x//b for x in l);return s-n and d(l,n,*[a,b,(a+b)/2,b*2][s>n::2])or b
def f(l,b,n):l=[[x*(x>=b*sum(sum(l,[])))for x in r]for r in l];return[[v//d(x,sum(x)//d(map(sum,l),n))for v in x]for x in l]

Probieren Sie es online!

Grundsätzlich nur ein Golf der Referenzimplementierung ...

Jelly , 63 36 Bytes

F×S<ḷ×ḷµ§⁵:,1_×¥:@"§IṠʋ÷9ɗ¥ƬṪṪƲ¥¥@⁺"

Probieren Sie es online!

Ein vollständiges Programm mit drei Argumenten: Anzahl der Stimmen in dem von der Frage beschriebenen Format, Takt und N in dieser Reihenfolge. Gibt eine Liste mit Sitzplatzzählern zurück. In der Fußzeile von TIO wird lediglich die Listenstruktur der Ausgabe hervorgehoben. (Andernfalls versteckt sich Jelly []für Einzelpostenlisten.)

Erläuterung

F×S<ḷ×ḷµ§⁵:,1_×¥:@"§IṠʋ÷9ɗ¥ƬṪṪƲ¥¥@⁺"

F                                   | Flatten vote counts
 ×                                  | Multiply by bar
  S                                 | Sum
   <ḷ                               | Less than original vote counts (vectorises and respects input list structure)
     ×ḷ                             | Multiply by original vote counts
       µ                            | Start a new monadic link with processed vote counts as input
        §                           | Vectorised sum

         ⁵                      ¥@  | Apply the following as a dyad with the number of seats as the right argument and the vectorised sum of votes as left

           ,                  Ʋ¥    |(*)- Pair vote counts with seat sum and find divisor using the following as a monad:
            1             ¥Ƭ        |     - Starting with 1 as a guess for divisor, and using the paired vote counts and seat sum as the right argument, apply the following as a dyad, collecting intermediate results, until the results repeat
                         ɗ          |       - Following as a dyad:
                      ʋ             |         - Following as a dyad:
                :@"                 |           - Integer divide with arguments zipped and reversed, i.e. divide cote counts by current divisor guess and leave total seats alone
                   §                |           -  Vectorised sum (will sum vote counts but leave seat number alone)
                    I               |           - Find differences i.e. desired total seats minus current calculation based on current divisor guess. Will return a list.
                     Ṡ              |           - Sign of this (-1, 0 or 1)
                       ÷9           |         - Divide by 9 (-0.111, 0 or 0.111)
             _×¥                    |     - Now multiply the current divisor guess by this and subtract it from that guess to generate the next guess. If the current guess is correct, the guess will be unchanged and so the Ƭ loop will terminate
                            ṪṪ      |     - Take the last item twice (first time to get the final
                               output of the Ƭ loop and second to remove the list introduced by I
         :                          | - Integer divide the vote counts by the output of the above

                                  ⁺"| Apply the above dyad from the step labelled (*) again, this time with the output of the previous step (total votes per coalition) as right argument and the vote counts as left argument, zipping the two together and running the link once for each pair

Ursprüngliche Einreichung (größer, aber effizienter)

Gelee , 63 Bytes

:S_3ƭƒṠ©ḢḤ;$;ṪƲṖÆm;ḊƲ®‘¤?ߥ/}ṛ¹?,
1,0;çḢḢ
FS×Ċ’<ḷ×ḷµ:"§:⁵ç$$ç"Ɗ

Probieren Sie es online!

Wolfram - kein Golf

War nur neugierig, es mit LinearProgramming zu lösen , kein Golfkandidat , aber vielleicht eine interessante Herangehensweise an ein Problem:

findDivisor[l_, n_] := Quiet@Module[{s, c, r, m, b, cons, sol},
   s = Length[l];
   c = Append[ConstantArray[0, s], 1];
   r = Thread[Append[IdentityMatrix[s], -l]];
   m = Append[Join[r, r], Append[ConstantArray[1, s], 0]];
   b = Append[Join[ConstantArray[{0, -1}, s], ConstantArray[{-1, 1}, s]], {n, 0}];
   cons = Append[ConstantArray[Integers, s], Reals];
   sol = LinearProgramming[c, m, b, 0, cons];
   {1/sol[[-1]], Most@sol}
   ]
solve[l_, bar_, n_] := 
 With[{t = l /. x_ /; x <= bar Total[l, 2] -> 0},
  With[{sol = findDivisor[Total /@ t, n]}, 
   {First@sol, MapThread[findDivisor, {t, Last@sol}]}]
  ]

Lesen Sie eine Erklärung und probieren Sie es aus!