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.
*murmel murmel* ... gewachsener Code ... *murmel murmel*
SCNR
