Hi,
Here is mail from Mike Ossipoff with code for SSD. I am also
including aj's Perl code that was used in the last election.
manoj
cloneproof_ssd.pl
Description: clone proof ssd
--- Begin Message ---Some time ago I sent to you a pasted copy of our website's Python program, to implement Cloneproof SSD, via the BeatpathWinner algorithm. Cloneproof SSD is abbreviated "CSSD". But that program doesn't include balloting. It has as its input the pairwise vote totals array, which in that program is called Pmat. That's the array that records how many people ranked each i over each j. But I didn't write that program, though I suggested the algorithm. Below, in this message, is a Python Cloneproof SSD program that I myself _did_ write. This way any errors in it are my own, and I can say that I've not been able to find any errors in this current version. The other advantage of this program is that it includes code that receives the rankings from the keyboard, prompting, for example, for "enter your choice # 3 candidate:" Of course this program also counts the rankings, to make the pairwise vote totals array. The previous program that I sent to you calls that array Pmat. This program calls it V. This is a little like "sending coals to Newcastle", sending software to professional programmers, who are incomparably more experienced than I am at program-writing. Still, as an advocate of Cloneproof SSD, it's my responsibility to offer count software of some kind. So now I'm sending you a complete count program written entirely by me, which is also my responsibility, however amateur a programmer I am. Anyway, it's important that a program make the completed pairwise vote totals array, because making that array is nearly the entire computational task of the pairwise-count methods such as CSSD. Of course, if you already have software that makes that pairwise vote totals array, you could put its values into V[A(i,j)], and just use the part of my program that uses that V array to determine the CSSD winner(s). In that case, find the line, near the bottom of the program, that says: W=[1]*N The block of lines just before that line is the beginning of the part of the program that you'd still use if you already had the pairwise vote total array. So you'd use that block and all that follows. And, add certain definition lines to a place just before that block: The definitions of the dictionary "cands", the variable N, the lists V & B, and the function A(i,j) should be moved to that position from their present positions earlier in the program. The reason why I write the pairwise vote totals array as V[A(i,j)] is because, instead of using 2-dimensional nested lists, I'm using 1-dimensional lists, with a function, A(i,j), which converts 2-dimensional array positions into 1-dimensional array positions. My balloting program doesn't recognize any such thing as a spoiled ballot. If the voter chooses to contradict himself in his ranking, he should be able to. It only reduces the effectiveness of his ballot, and that's his doing and his problem. In my 3-nested for loops that find the strongest beatpath from each i to each j, I don't include requirements that i not equal j or k, etc. That's because leaving such requirements out has no effect on the winner(s), and so I leave it out for simplicity. In case the program will be used with its balloting part, let me say something about how that works: The balloting has 2 parts. Part 1 asks for & receives the names, abbreviations, or initials of the candidates (or alternatives). Part 2 receives the rankings. In part 1, the user is asked for candidate names, and enters each one when prompted for it. If you want to correct an entry error, by redoing the previous entry, enter 1. The program will then receive the replacement for that incorrect name that you want to replace. When done with the names, enter 0 (the zero key). In part 2, when asked, for instance, for "choice #3, enter that ranking's 3rd choice. Then, when prompted for "choice #4, and if you want to enter an additional 3rd choice (because you can enter as many choices at any rank position as you want to), enter 1. The program will say "enter more choice #3". If you want to redo the most recent entry, enter 2. If you want to redo the entire current ranking, enter 3. When finished with the current ranking, enter 0 (the zero key). When done entering all the rankings, enter 9. One more thing: I don't have a computer, and so I haven't been able to test this program. But I've checked it for errors, including typos. At first I found a number of them. Then I couldn't find any. So there's a good chance that there aren't any now. But if it doesn't run as intended, maybe the error will be some obvious typo or other obvious error that you can fix. Otherswise, you could send to me the error message, and I could fix the error. Of course when I get a computer I can send a program that I've tested and which I can guarantee to contain no typos. Have I left anything out? Anyway, very likely Debian, an organization of programmers, will have no use for this program. But, as I said, as an advocate of CSSD, I still have a responsibility to send CSSD count software where CSSD has been adopted. Oh, one last thing, I'm just pasting the Python listing into e-mail. I hope that the indentations don't get scrambled by e-mail. If they do, let me know, and I'll add "endwhile", "endif", etc., to show where the ends of the blocks are supposed to be, so that you can fix the indentations. Of course the "enwhile" and "endif", etc., should then be removed, since Python doesn't use them, but instead uses the indentations to delimit "if" and "while" blocks. Another alternative, if the indentations don't survive e-mail, would be to tell me how to send the program by ftp or something, some way that wouldn't scramble the indentations. Well maybe they'll arrive ok in this e-mail. Anyway, here's the Python program to receive the candidate list and then the rankings, and then use them to determine the winner by Cloneproof SSD, via the BeatpathWinner algorithm: def CSSD(): cands={} number={} index=0 done=0 print "enter candidate names or initial(s)" while done=0 reenter=1 while reenter=1 print "next candidate" cnd=raw_input() if cnd="1" del number[cands[lastn]] del cands[lastn] index=lastn else reenter=0 if cnd="0" print "all candidates entered" print "enter rankings" done=1 else cands[index]=cnd number[cnd]=index lastn=index index=index+1 N=len(cands) M=N+100 rank=[M]*N V=[0]*N**2 B=[0]*N**2 def A(i,j): return N*i+j for i in range(N) for j in range(N) V[A(i,j)]=0 doneall=0 while doneall=0 for i in range(N) rank[i]=N+100 rankn=0 donethis=0 while donethis=0 rankn=rankn+1 reenter=1 while reenter=1 print "choice # ",rankn,":" cnd=raw_input() if cnd="1" print "enter more choice #", rankn elif cnd="2" print "re-do most recent entry" rank[lastn]=N+100 rankn=lastn else reenter=0 if cnd="3" print "redo current ranking" for i in range(N) rank[i]=N+100 rankn=0 elif cnd="0" print "next ranking" donethis=1 elif cnd="9" print "All rankings are entered." print "Program is running and will" print "shortly report Cloneproof SSD" print "winner(s), determined by print "BeatpathWinner algorithm" donethis=1 doneall=1 for i in range(N) for j in range(N) if rank[j]>rank[i] V[A(i,j)]=V[A(i,j)]+1 for i in range(N) for j in range(N) if V[A(i,j)]>V[A(j,i)] B[A(i,j)]=V[A(i,j)] else B[A(i,j)]=0 W=[1]*N repeat=1 while repeat=1 change=0 for i in range(N) for j in range(N) for k in range(N) low=min(B[A(i,j)],B[A(j,k)] if low>B[A(i,k)] B[A(i,k)]=low change=1 if change=0 repeat=0 for i in range(N) W[i]=1 for i in range(N) for j in range(N) if B[A(i,j)]>B[A(j,i)] W[j]=0 for i in range(N) if W[i]=1 print cands[i],"wins" _______________ __________________________________________________ Do you Yahoo!? HotJobs - Search new jobs daily now http://hotjobs.yahoo.com/
--- End Message ---
-- Please don't ask me what the score is, I'm not even sure what the game is. Ashleigh Brilliant Manoj Srivastava <[EMAIL PROTECTED]> <http://www.debian.org/%7Esrivasta/> 1024R/C7261095 print CB D9 F4 12 68 07 E4 05 CC 2D 27 12 1D F5 E8 6E 1024D/BF24424C print 4966 F272 D093 B493 410B 924B 21BA DABB BF24 424C
