leah blogs: Determining an election in k

leah blogs

« X11 screen locking: a secure and modular approach<br>March 2020<br>Shrinking multiple TeX Live installations »

18mar2020 ·

Determining an election in k

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

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

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

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

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

v: 10400 3400 6200<br>s: 15

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

!s<br>0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

(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<br>characteristic of Sainte-Laguë:

.5+!s<br>0.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 10.5 11.5 12.5 13.5 14.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 (')<br>operator so say we want the whole list of votes to be divided by each<br>divisor:

v % 0.5<br>20800 6800 12400f<br>v % 1.5<br>6933.333 2266.667 4133.333

(v%)'.5+!s<br>20800 6800 12400<br>6933.333 2266.667 4133.333<br>4160 1360 2480<br>2971.429 971.4286 1771.429<br>2311.111 755.5556 1377.778<br>1890.909 618.1818 1127.273<br>1600 523.0769 953.8462<br>1386.667 453.3333 826.6667<br>1223.529 400 729.4118<br>...

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<br>operator (,) over the table (/):

,/r<br>20800 6800 12400 6933.333 2266.667 4133.333 4160 1360 2480 2971.429 ...

Now we can sort this list, using the new ^ operator:

^,/r<br>234.4828 251.8519 272 295.6522 323.8095 357.8947 400 427.5862 453.3333 ...

But we actually want the biggest numbers, so let’s reverse this:

|^,/r<br>20800 12400 6933.333 6800 4160 4133.333 2971.429 2480 2311.111 2266.667 ...

Now we can take as many as we have seats:

s#|^,/r<br>20800 12400 6933.333 6800 4160 4133.333 2971.429 2480 2311.111 2266.667 1890.909 1771.429 1600 1386.667 1377.778

Great. Now, we have to find (?) these in the original table:

((s#|^,/r)?)'r<br>0 3 1<br>2 9 5<br>4 15 7<br>6 15 11<br>8 15 14<br>10 15 15<br>12 15 15<br>13 15 15<br>15 15 15<br>...

Find returns the index of the left side in the right side,<br>or an index out of bounds if it can’t find the element.<br>If we check this table for s, we can detect these elements:

s=((s#|^,/r)?)'r<br>000<br>000<br>010<br>010<br>010<br>011<br>011<br>011<br>111<br>...

But we actually want the negation (~) of this table:

~s=((s#|^,/r)?)'r<br>111<br>111<br>101<br>101<br>101<br>100<br>100<br>100<br>000<br>...

Now, we just have to sum (+) up (/) the columns again:

+/~s=((s#|^,/r)?)'r<br>8 2 5

This is the seat assignment per party now!

In good k manner, we fuse this program into a single line (assignment<br>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<br>when multiple parties get the same votes, for example:

v:7 7 7<br>s:20<br>+/~s=((s#|^,/r)?)'r:(v%)'.5+!s<br>7 7 7

Oops.

We can fix the solution, and actually even make it shorter (but a<br>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<br>0 2 3 1 6 5 9 8 12 4 15 11 18 21 14 7 24 17 27 30 10 20 33 36 23 39 13 26 42 29 16 32 35 19 38 41 22 44 25 28 31 34 37 40 43

What does this mean? It says the biggest number is the 0th element,<br>the second biggest number is the 2nd element, the third biggest number<br>is the 3rd element, and so on.

This is not directly useful, but a well-known trick is to grade-down ()<br>this list now:

<>,/r<br>0 3 1 2 9 5 4 15 7 6 20 11 8 26 14 10 30 17 12 33 21 13 36 24 16 38 27 18 39 29 19 40 31 22 41 32 23 42 34 25 43 35 28 44 37

And this is actually the rank of each seat!<br>(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<br>the new cut (^) operator that replaces the reshape operator.<br>As we have as many columns as votes, we get:

(#v)^<>,/r<br>0 3 1<br>2 9 5<br>4 15 7<br>6 20 11<br>8 26 14<br>10 30 17<br>...

But again, we are only interested in the seats less than s, so

s>(#v)^<>,/r<br>111<br>111<br>101<br>101<br>101<br>100<br>100<br>100<br>000<br>...

And we can sum up...