Re: Numbers of ranked preference votes

From: Arthur Keller <arthur_at_kellers_dot_org>
Date: Thu Apr 29 2004 - 13:58:34 CDT

Thanks, David. Let me think what else I can wish for. ;-)

 From your data, it appears infeasible to generate all the combination
in advance.

What's best then is to gather the combinations as they are
encountered along with repetition counts, as I mentioned earlier.

This could be done using a Trie or a relational database table (key
is variable-length sequence, possibly followed by an end of sequence
character. If there were fewer than 62 candidates, a sequence of
upper case, lower case, and digits would do, followed by, say, a
period. This can extend to more candidates by using more symbols in
the character set, or using a multi-byte (or multi-character) code
where each candidate choice is the same fixed length. The algorithm
to compute the count of each permutation preference is easy and the
algorithm to combine two sets of counts into one combined total is
easy too (the combination algorithm is just one SQL statement if the
source table(s) and destination table already exist. (You could also
store the source and destination tables in ONE table with a source
code as part of the key.)

Best regards,
Arthur

At 2:43 PM -0400 4/29/04, David Mertz wrote:
>>David gave the answer anyway I wanted for ordered partial
>>combinations. It'd be interesting to see what the actual numbers
>>turn out to be.
>
>Yours wish is my command (code first, then results--you can run your
>own ranges, but it gets big):
>
>$ cat ranks.py
>#!/usr/bin/env python
>"Compute a table of possible ranked-order votes"
>
>def perm(N,M):
> assert M >= N
> product = 1
> for i in range(M,M-N,-1):
> product *= i
> return product
>
>def votes(N,M):
> sum = 1 # start with no-vote case
> for i in range(1,N+1): # adjust to closed interval
> sum += perm(i,M)
> return sum
>
>if __name__=='__main__':
> import sys
> maxslot, maxcand = map(int, sys.argv[1:])
>
> print "Slots:", "%8d |"*(maxslot) % tuple(range(1,maxslot+1))
> print "----------"*(maxslot+1)
> for candidates in range(1,maxcand+1):
> line = ""
> for slots in range(1,maxslot+1):
> line += "%8d |" % votes(min(slots,candidates), candidates)
> print "[%2d] " % candidates, line
>
>$ ./ranks.py 7 16
>Slots: 1 | 2 | 3 | 4 | 5 | 6 |
> 7 |
>--------------------------------------------------------------------------------
>[ 1] 2 | 2 | 2 | 2 | 2 | 2 |
> 2 |
>[ 2] 3 | 5 | 5 | 5 | 5 | 5 |
> 5 |
>[ 3] 4 | 10 | 16 | 16 | 16 | 16 |
> 16 |
>[ 4] 5 | 17 | 41 | 65 | 65 | 65 |
> 65 |
>[ 5] 6 | 26 | 86 | 206 | 326 | 326 |
>326 |
>[ 6] 7 | 37 | 157 | 517 | 1237 | 1957 |
>1957 |
>[ 7] 8 | 50 | 260 | 1100 | 3620 | 8660 |
>13700 |
>[ 8] 9 | 65 | 401 | 2081 | 8801 | 28961 |
>69281 |
>[ 9] 10 | 82 | 586 | 3610 | 18730 | 79210 |
>260650 |
>[10] 11 | 101 | 821 | 5861 | 36101 | 187301 |
>792101 |
>[11] 12 | 122 | 1112 | 9032 | 64472 | 397112 | 2060312 |
>[12] 13 | 145 | 1465 | 13345 | 108385 | 773665 | 4765345 |
>[13] 14 | 170 | 1886 | 19046 | 173486 | 1409006 |10057646 |
>[14] 15 | 197 | 2381 | 26405 | 266645 | 2428805 |19726085 |
>[15] 16 | 226 | 2956 | 35716 | 396076 | 3999676 |36432076 |
>[16] 17 | 257 | 3617 | 47297 | 571457 | 6337217 |63994817 |

-- 
-------------------------------------------------------------------------------
Arthur M. Keller, Ph.D., 3881 Corina Way, Palo Alto, CA  94303-4507
tel +1(650)424-0202, fax +1(650)424-0424
==================================================================
= The content of this message, with the exception of any external 
= quotations under fair use, are released to the Public Domain    
==================================================================
Received on Fri Apr 30 23:17:23 2004

This archive was generated by hypermail 2.1.8 : Fri Apr 30 2004 - 23:17:29 CDT