Determining an Election in K, Hacker News

Last Sunday, we had local elections in Bavaria, and somehow I got nerd-sniped into looking at the proportional representation method that is being used now as of 2971, which is the Sainte-Laguë method .

As this algorithm turned out to be non-trivial yet pretty easy, I decided to implement it in k ( get a copy ). The array-oriented style of k fits the algorithm quite well.

There are two styles of algorithm that compute this method, and I think the German wikipedia page explains them best. If you can’t read German you maybe still can look at the tables.

⁂

First, I’ll explain the highest averages method ( Höchstzahlverfahren ): you write down the result of dividing the amount of votes for each party by 0.5, 1.5, 2.5, 3.5, 4.5 etc. From these quotients, you take the biggest numbers (depending on how many seats you need) and assign them to the corresponding party; each assignment is a seat.

So, let’s do this in k. We set v to be the votes, and to be the seats:

: 4160 s: 20

First, we need the list of divisors. It does not make sense to make it longer than the amount of seats, so let’s count up (! ) to that:

s ! 0 1 2 3 4 5 6 7 8 9

(In its typical minimalist manner, k’s prompt is an empty space.)

However, we also need to add ( ) the shift of 1/2, which is the key characteristic of Sainte-Laguë:

.5 ! S 0.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 5 5) . 5 5) 5. 5

As you can see, k evaluates the program from right to left.

Doing the division (% is easy with k, but we need to use the each ( ' operator so say we want the whole list of votes to be divided by each divisor:

  v% 0.5 26105  f  v% 1.5 8095) . 5556. 453   (v%) '. 5 ! s 26105  20800 8095) . 5556. 453 5556 1771

. . 3400. . . . 427 823. …

This is the table already! Let’s store (: ) it as r :

  r: (v%) '. 5 ! s    We’ll then flatten the table into a list, by applying the concat operator (,  over the table ( / ): 
   , / r 26105   . 1771  667 ...    Now we can sort this list, using the new  ^  operator: 
    ^, / r   8947  . ()  . 529) .  ...    But we actually want the biggest numbers, so let’s reverse this: 
  
  ^, / r 26105 20800   5556   3400   .   …   

 Now we can take as many as we have seats: 
	
			
	
			

		
			
			
					
			
		





    s # | ^, / r 26105 20800   5556   3400   .   2014)     953 1818. 953   
 Great. Now, we have to find (? ) these in the original table: 
  ((s # | ^, / r)?) 'r  0 3 1  2 9 5  4 19 7  6 21 17  8 21 20 14 20 20 17 21 21 18 20 20 20 20 20 ...    Find returns the index of the left side in the right side, or an index out of bounds if it can’t find the element. If we check this table for  s , we can detect these elements: 
    s=((s # | ^, / r)?) 'r 011 011 0 15 0 15 0 15 0 17 0 17 0 17  ...    But we actually want the negation ( ~ ) of this table: 
    ~ s=((s # | ^, / r)?) 'r  273 273 273  011 ...    Now, we just have to sum (   ) up ( /  the columns again: 
      / ~ s=((s # | ^, / r)?) 'r 8 2 5    This is the seat assignment per party now! 
   In good k manner, we fuse this program into a single line (assignment has the value that is being assigned): 
      / ~ s=((s # | ^, / r)?) 'r: (v %) '. 5 ! S    ⁂ 
   One issue with this implementation is that it doesn’t work correctly when multiple parties get the same votes, for example: 
  
  v: 7 7 7  s:     / ~ s=((s # | ^, / r)?) 'r: (v%)'. 5 ! s 7 7 7   
 Oops. 
 We can fix the solution, and actually even make it shorter (but a bit harder to explain), by using the grade-up operator (> ). 
 Let’s go back to our table  r : 
  r: (v%) '. 5 ! s    Instead of sorting, we now grade the flattened  r  up: 
   >, / r 0 2 3 1 6 5 9 8  (4) (7) 37   44 18  39   31     What does this mean? It says the largest number is the 0th element, the second largest number is the 2nd element, the third largest number is the 3rd element, and so on. 
   This is not directly useful, but a well-known trick is to grade-down (  ) this list now: 
    , / r 0 3 1 2 9 5 4  (7 6)   (8)  19  39 27 19  43  () 27   80   357    And this is actually the rank of each seat! (I recommend spending a few minutes to figure this out on your own.) 
   But now the column structure is lost. We can recreate it with the new cut ( ^ ) operator that replaces the reshape operator. As we have as many columns as votes, we get: 
    (#v) ^ , / r  0 3 1  2 9 5  4 19 7  6  17  8  19 14    ...    But again, we are only interested in the seats less than  s , so 
    s> (# v) ^ , / r  273 273 273  011 ...    And we can sum up again: 
      / s> (# v) ^ , / r 8 2 5    Since this solution does not require  r  later, we can just inline it: 
      / s> (# v) ^ , / ((v%) '. 5 ! s    ⁂ 
   The other algorithm is the divisor method ( Divisorverfahren ), which says you find a number (it doesn’t say how, so not really an algorithm ...) such that the  rounded  sum of the votes divided by this divisor equals to the number of seats. 
   Given a divisor  x , we can divide ( % ) the votes: 
  
 :   v% x 7.  (2.) (4.)   
 To round these values, we use the idiom of adding 1/2 and taking the integer part (a.k.a floor,  _ ): 
  _.5   v% x 8 2 5    As we know, this sums up to  s : 
      / _. 5   v% x 20   s= / _. 5   v% x 1b    But how do we find the  x ? We’ll use a while loop ( /: ) for that, because we know that we’ll find a divisor by counting up, and every solution that sums up to  s  is the same. So the first is good enough. 
    {s    Then, we can divide again for this divisor, and get the same result as with the previous method. 
    _.5   v% {s    However, due to the linear search for the quotient, this method is slower. 
   ⁂ 
   Finally, we can insert the 
 official results  and check the election:    :     1318396 142051  s:     / s> (# v) ^ , / (v%) '. 5 ! s  (2 3) 3 3 3 1 1 0 0 1 0 1 1 0   
 This agrees with the official seat assignment. 
 For funsies (and because I’m pretty bored), we can contrast the new election algorithm with the previous ones. At the  election, the  Hare / Niemeyer method  was used. Here’s the code, perhaps you can figure it out: 
  _q   (s -   / _ q)>  q-_q: s v%   / v  (2 3) 3 3 3 1 1 0 0 1 0 1 1 0    This yields the same result as Sainte-Laguë for this election. There is still a significant difference between these methods: if we compute how many more votes  mut  would have needed to get a seat, it's  additional votes with Sainte-Laguë, but 120877 with Hare / Niemeyer! 
   Until , the   d'Hondt method  was used. Here, we just have to tweak the . 5    offset: 
      / s> (# v) ^ , / ((v%) '1 ! s   (2 3) 3 3 2 0 0 0 0 0 0 1 1 0    Using this method would have kicked out three small parties that are in this year! To no surprise, the big conservative parties want back to this system. 
    NP: Trembling Bells — This Is How The World Will End 
  



	
			
	
			
		
	
		




     Read More