#9 Failing check for duplicate random nums

closed
Roy Ward
Algorithm (3)
4
2003-03-13
2002-12-08
No

From code inspection, I suspect that the array of candidate random numbers (candRand[]) used for breaking ties may sometimes contain duplicate values. I believe that the intent is for this array to have no duplicate values. The array is initialised with a random number for each candidate, and it is used for breaking ties. Allowing duplicates still allows for tiebreakers, but in a different way than expected, and perhaps (I haven't thought it through) not as fairly.

Here is the location of the suspected error. In STV.java v0.4 line 94, there is an if statement
if(n == candRand[i]) {
The subscript should be "j" instead, I believe.

Subscript i is indexing through candRand[], and i represents the entry currently being populated. j indexes through the already-populated portion of candRand[], from 0 to i-1. An expression (n == candRand[i]) will evaluate the same for each value of j, and doesn't check the candidate random number against any of the populated values in candRand[]. An expression of candRand[j] will check the populated values of candRand[] methodically.

This bug would have been caught if there had been a separate set of loops at the end of the initialisation of candRand[] which asserted that no entry had the same value as any other entry.

Discussion

    • labels: --> Algorithm
    • priority: 5 --> 4
    • assigned_to: nobody --> royward0
     
  • Roy Ward
    Roy Ward
    2003-03-13

    • status: open --> closed
     
  • Roy Ward
    Roy Ward
    2003-03-13

    Logged In: YES
    user_id=63302

    That is the correct fix. Done, and will be included in the
    next release shortly.