[EM] IRV is summable (a little)

[Roy]

One of the commonly cited problems of IRV is that it is not summable: 
to process the ballots, they must be re-read, or a count must be made 
of the ballots matching each possible ballot, which requires N! 
figures to be kept.

That's not quite true. It is only necessary to remember which 
candidates (if any) are ranked ahead of a candidate to know whether 
and when votes for him should be counted. The order of the candidates 
ahead of him are not important. That means that IRV ballots are 
summable in a total of N * 2^N figures. A fair improvement over N!. 
(Actually, it's N * 2^(N-1), but that gets clumsy to implement).

One implementation would be to have a bit-vector of one bit per 
candidate in some predetermined order. When examining a ballot, look 
at each candidate and determine which candidates are ahead of her. 
Set the bits in the bit vector to represent that, and use the 
resulting number as an index into a 2-D array, where the other index 
is the position of the candidate being evaluated.

The only figures of interest in tallying are those whose bit-vector 
index is (all) zero. Easy enough. When a candidate is eliminated, the 
array is searched for all entries where that candidate's bit is on, 
and the tallies are added to the counts where that candidate's bit is 
off (and all other bits are the same).