Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Code-Stücke können hier veröffentlicht werden.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon Rebecca » Montag 10. Juli 2006, 16:02

Wenn man etwas proportional zu gegebenen Groessen aufteilen will, aber nur Integerwerte vorkommen duerfen (zum Beispiel wenn man den Fortschritt eines Programms auf die Pixel oder Zeichen eines Fortschrittbalkens abbilden will), hilft einem reine Prozentrechnung nicht weiter. Deswegen habe ich das Hare-Niemeyer-Verfahren (Hamilton-Verfahren) programmiert, welchs auch bei der Verteilung der Sitze im Bundestag Anwendung findet.

Code: Alles auswählen

def hamilton_allocation(counts, alloc):
    """
    Implements the Hamilton Method (Largest remainder method) to calculate
    integral ratios. (Like it is used in some elections.)

    counts -- list of integers ('votes per party')
    alloc -- total amount to be allocated ('total amount of seats')
    """

    total_counts = sum(counts);
    quotas = [float(count)*alloc/total_counts for count in counts]

    fracts = []
    for (i, fp) in enumerate(quotas):
        fracts.append((math.modf(fp)[0], i))
       
    fracts.sort()
    fracts.reverse()

    results = [int(math.modf(quota)[1]) for quota in quotas]   
    remainder = alloc - sum(results)

    for (fract, i) in fracts:
        results[i] += 1
        remainder -= 1
        if remainder == 0: break
   
    return results       


Beispiel: Vier Parteien haben je 216, 310, 22 und 32 Stimmen, und es sollen 100 Sitze verteilt werden:

Code: Alles auswählen

>>> hamilton_allocation([216, 310, 22, 32], 100)
[37, 53, 4, 6]

D.h. die Parteien erhalten 37, 53, 4 und 6 Sitze.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Montag 10. Juli 2006, 16:56

Hi

Der Code sieht schön aus.

Aber noch ein paar kleine Vorschläge & Fragen:

Warum hast du bei Zeile 14 nicht auch eine List Comprehension gemacht?

Code: Alles auswählen

fracts = [(math.modf(fp)[0], i) for (i,fp) in enumerate(quotas)]


Beim Sortieren kannst du mit reverse=True direkt umgekehrt sortieren

Code: Alles auswählen

fracts.sort(reverse=True)


Und bei Zeile 23 fände ich diese For-Schleife passender:

Code: Alles auswählen

    for i in range(remainder):
        results[fracts[i][1]] += 1



Gruss
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Beitragvon Rebecca » Dienstag 11. Juli 2006, 07:32

rayo hat geschrieben:Der Code sieht schön aus.
Danke.

rayo hat geschrieben:Warum hast du bei Zeile 14 nicht auch eine List Comprehension gemacht?
Keine Ahnung. Manchmal finde ich die Dinger unuebersichtlich, aber in diesem Fall sieht's ja doch gar nicht so schlimm aus als List Comprehension. :wink:

rayo hat geschrieben:Beim Sortieren kannst du mit reverse=True direkt umgekehrt sortieren
Ja, nur leider muss ich 2.2-kompatibel bleiben. :?

rayo hat geschrieben:Und bei Zeile 23 fände ich diese For-Schleife passender:

Code: Alles auswählen

    for i in range(remainder):
        results[fracts[i][1]] += 1

Jo, da haste man recht! :lol: *murmel murmel* ... gewachsener Code ... *murmel murmel*
theinfmonkey
User
Beiträge: 7
Registriert: Dienstag 24. August 2010, 08:59

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon theinfmonkey » Dienstag 24. August 2010, 09:54

Hab deinen Code genutzt um in einer Epidemiesimulation keine gebrochenzahligen Individuen rumstehen zu haben...

Danke.
Anfänger.
Benutzeravatar
/me
User
Beiträge: 3157
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon /me » Dienstag 24. August 2010, 10:57

theinfmonkey hat geschrieben:Hab deinen Code genutzt um in einer Epidemiesimulation keine gebrochenzahligen Individuen rumstehen zu haben...

Die Epidemie ist sicher auch für spontane Platzvermehrung zuständig:

Code: Alles auswählen

>>> print(hamilton_allocation([5, 5], 10))
[6, 6]
>>> print(hamilton_allocation([5.01, 5], 10))
[5, 5]

Das ist eine böse Falle, wenn die Gesamtzahl der zu verteilenden Plätze gleich der Summe der "votes per party" ist.
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon derdon » Dienstag 24. August 2010, 18:23

Warum benutzt du LCs, wenn GCs ebenfalls funktionieren (und den Vorteil haben, schneller zu sein, da auf iteration optimiert)?
Benutzeravatar
/me
User
Beiträge: 3157
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon /me » Dienstag 24. August 2010, 20:00

derdon hat geschrieben:Warum benutzt du LCs, wenn GCs ebenfalls funktionieren (und den Vorteil haben, schneller zu sein, da auf iteration optimiert)?

Nun, das dürfte daran liegen, dass Rebeccas Posting über 4 Jahre alt ist, der Code noch mit Python 2.2 laufen sollte und Generator Expressions IIRC erst mit Python 2.4 eingeführt wurden.
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon derdon » Dienstag 24. August 2010, 20:12

Oh, ich habe einfach angenommen, der erste Post aus diesem Thread wäre ebenfalls neu. Habe nicht mit Leichenschändern gerechnet. :twisted:
Benutzeravatar
jbs
User
Beiträge: 953
Registriert: Mittwoch 24. Juni 2009, 13:13
Wohnort: Postdam

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon jbs » Dienstag 24. August 2010, 22:46

Warum ist da eigentlich ein Semikolon.

Code: Alles auswählen

total_counts = sum(counts);
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon Hyperion » Dienstag 24. August 2010, 23:20

jbs hat geschrieben:Warum ist da eigentlich ein Semikolon.

Warum liegt hier eigentlich Stroh? :mrgreen: SCNR

Vermutlich war Rebecca da relativ neu bei Python und kam aus ner C-Dialekt / Syntax Ecke? Wäre jetzt mal meine Vermutung... Oh Gott, wir betreiben schon Thread-Archäologie :-D
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3))
assert encoding_kapiert
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon Leonidas » Mittwoch 25. August 2010, 00:06

Hyperion hat geschrieben:
jbs hat geschrieben:Warum ist da eigentlich ein Semikolon.

Warum liegt hier eigentlich Stroh? :mrgreen: SCNR

Genau, und warum nicht ``sorted()`` und ``reversed()`` :P

Aber passt nur auf, nicht dass jemand eure alten Posts rausholt und auslacht :twisted:
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon hendrikS » Mittwoch 25. August 2010, 04:19

Ich hab mir's auch mal kopiert. Kann nicht schaden.
Vereinfacht habe ich nur:

Code: Alles auswählen

int(math.modf(quota)[1])

zu

Code: Alles auswählen

int(quota)
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon Hyperion » Mittwoch 25. August 2010, 09:55

Leonidas hat geschrieben:Aber passt nur auf, nicht dass jemand eure alten Posts rausholt und auslacht :twisted:

Da müßte man bei mir nicht mal so lange zurück blicken ;-)
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3))
assert encoding_kapiert
Benutzeravatar
jbs
User
Beiträge: 953
Registriert: Mittwoch 24. Juni 2009, 13:13
Wohnort: Postdam

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon jbs » Mittwoch 25. August 2010, 13:12

/me hat geschrieben:
theinfmonkey hat geschrieben:Hab deinen Code genutzt um in einer Epidemiesimulation keine gebrochenzahligen Individuen rumstehen zu haben...

Die Epidemie ist sicher auch für spontane Platzvermehrung zuständig:

Code: Alles auswählen

>>> print(hamilton_allocation([5, 5], 10))
[6, 6]
>>> print(hamilton_allocation([5.01, 5], 10))
[5, 5]

Das ist eine böse Falle, wenn die Gesamtzahl der zu verteilenden Plätze gleich der Summe der "votes per party" ist.


Der Fehler liegt in der for-Schleife. Man sollte zuerst schauen, ob es noch was zu verteilen gibt, bevor man Sitze vergibt. Denn wenn es von Anfang keine Sitze überbleiben wird der remainder negativ und alle bekommen einen Sitz. So gehts:

Code: Alles auswählen

for (fract, i) in fracts:
        if remainder == 0: break
        results[i] += 1
        remainder -= 1


Ein Losentscheid müsste man noch einbauen, denn so hat immer der letzte der Liste einen Vorteil.
theinfmonkey
User
Beiträge: 7
Registriert: Dienstag 24. August 2010, 08:59

Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)

Beitragvon theinfmonkey » Freitag 27. August 2010, 10:40

Ohne Losentscheid entsteht tatsächlich folgenes Problem:

Code: Alles auswählen

>>> print hamilton_allocation([3,2,1], 3)
[1, 1, 1]
>>> print hamilton_allocation([1,2,3], 3)
[0, 1, 2]


Losverfahren lässt sich allerdings schnell einbauen:

Code: Alles auswählen

import math, random

def hamilton_allocation(counts, alloc):
   
    total_counts = sum(counts);
    quotas = [count*alloc/total_counts for count in counts]

    fracts = [(math.modf(fp)[0], i) for (i,fp) in enumerate(quotas)]

    fracts.sort(reverse=True)

    results = [int(math.modf(quota)[1]) for quota in quotas]
    remainder = alloc - sum(results)

    #make list of indices and shuffle it
    indices = range(len(results))
    random.shuffle(indices)

    for i in xrange(remainder):
        #add to random element in results
        results[indices.pop()] += 1

    return results


Testing zeigt einerseits die zufällige Zuordnung der verbliebenen Sitze, sowie die Lösung des Problems des Sitzwachstums

Code: Alles auswählen

import unittest

class HamiltonAllocationTest(unittest.TestCase):

    def test_random_allocation(self):

        "tests random allocation"

        #equal distribution of counts should return random
        #allocation of a single seat
        results = [[1,0,0],[0,1,0],[0,0,1]]

        #try max. 100 times
        for i in xrange(100):

            result = hamilton_allocation([1,1,1], 1)

            if result in results:
                results.remove(result)

            #all results occurred
            if results == []: break

        #test only successful if for-loop left by break
        self.failUnlessEqual(results, [])



    def test_erroneous_seat_growth(self):

        "tests for programming mistake in first version -> see link"

        #due to random allocation of last seats only sums can be tested
        self.failUnlessEqual(sum(hamilton_allocation([5, 5], 10)), 10)
        self.failUnlessEqual(sum(hamilton_allocation([5.01, 5.00], 10)), 10)




if __name__ == "__main__":
    unittest.main()


Code: Alles auswählen

..
----------------------------------------------------------------------
Ran 2 tests in 0.001s

OK


Ich weiss allerdings nicht, ob das im engeren Sinne noch Hare-Niemeyer ist.

Darüber hinaus sollten nach meiner Intuition die Wahscheinlichkeiten für [6, 4] zu [5, 5] für

Code: Alles auswählen

hamilton_allocation([5.1, 5.00], 10)
hamilton_allocation([5.000001, 5.00], 10)


verscheiden sein, was in meiner Implementation nicht der Fall ist.

P.S. Ich rufe hamilton_allocation() während meiner Simulation ca. 10e7 mal auf. Für Optimierungen bin ich also dankbar. :)
Anfänger.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder