Seite 1 von 1
Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Montag 10. Juli 2006, 16:02
von Rebecca
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.
Verfasst: Montag 10. Juli 2006, 16:56
von rayo
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
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
Verfasst: Dienstag 11. Juli 2006, 07:32
von Rebecca
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.
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!
*murmel murmel* ... gewachsener Code ... *murmel murmel*
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 09:54
von theinfmonkey
Hab deinen Code genutzt um in einer Epidemiesimulation keine gebrochenzahligen Individuen rumstehen zu haben...
Danke.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 10:57
von /me
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.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 18:23
von derdon
Warum benutzt du LCs, wenn GCs ebenfalls funktionieren (und den Vorteil haben, schneller zu sein, da auf iteration optimiert)?
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 20:00
von /me
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.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 20:12
von derdon
Oh, ich habe einfach angenommen, der erste Post aus diesem Thread wäre ebenfalls neu. Habe nicht mit Leichenschändern gerechnet.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 22:46
von jbs
Warum ist da eigentlich ein Semikolon.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Dienstag 24. August 2010, 23:20
von Hyperion
jbs hat geschrieben:Warum ist da eigentlich ein Semikolon.
Warum liegt hier eigentlich Stroh?
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
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Mittwoch 25. August 2010, 00:06
von Leonidas
Hyperion hat geschrieben:jbs hat geschrieben:Warum ist da eigentlich ein Semikolon.
Warum liegt hier eigentlich Stroh?
SCNR
Genau, und warum nicht ``sorted()`` und ``reversed()``
Aber passt nur auf, nicht dass jemand eure alten Posts rausholt und auslacht
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Mittwoch 25. August 2010, 04:19
von hendrikS
Ich hab mir's auch mal kopiert. Kann nicht schaden.
Vereinfacht habe ich nur:
zu
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Mittwoch 25. August 2010, 09:55
von Hyperion
Leonidas hat geschrieben:
Aber passt nur auf, nicht dass jemand eure alten Posts rausholt und auslacht
Da müßte man bei mir nicht mal so lange zurück blicken
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Mittwoch 25. August 2010, 13:12
von jbs
/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.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Freitag 27. August 2010, 10:40
von theinfmonkey
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.
Re: Hare-Niemeyer-Verfahren (Hamilton-Verfahren)
Verfasst: Samstag 25. September 2010, 19:47
von birkenfeld
/me hat geschrieben: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.
Und inzwischen ist ihr OP auch noch teilweise falsch