ranking and tie breaking

[sneakyimp]

i have an array with 6 scores. it might be something like this:

$arr['a'] = 16;
$arr['b'] = 27;
$arr['c'] = 6;
$arr['d'] = 34;
$arr['e'] = 54;
$arr['f'] = 3;

my task is to determine the KEY of the top 2 scores. for this particular array, it's pretty simple, but when i have a tie, i need to use a tie-breaking function i have which, based on some other criteria, can be used to break a tie.

that might still sound pretty simple, but suppose all 6 scores are tied? in theory, this could happen.

my first inclination was to sort the array using arsort and use the first two items. that works fine when there's no tie, but when there's a six-way tie, it's woefully inadequate.

it occurred to me that this sort of logic might have been handled by someone else calculating sports scores or something so i thought i'd ask if any had some suggestions about it before i start running down a variety of blind alleys.

[mtmosier]

Are you asking us how to make sure all six are never tied? I don't believe that's a php problem. Perhaps you could rig the contest...

You probably want to sort them, taking into account tie-breakers when they're equal. Depending on how your tie-break function works, it sounds like a job for uasort.

[sneakyimp]

uasort rocks. just ran little test and that seems to be what i need.

however, i've just realized something. the transitive propery of inequality doesn't really fully apply here. it does to the simple values for each array key, but when the tie breaking function kicks in, you could get a situation where:

a > b
b > c
c > a

doh!

this is for a skill/interest/personality test kind of thing (NO it's not scientology). the guy who worked on the test (statistician kind of guy) assures me that no 6-way tie is possible, but a 2, 3, or 5-way tie is possible. our tiebreaking algorithm can only guarantee resolution between 2 tied values.

my instinct tells me there is no general perfect solution to this problem if transitivity doesn't hold up. we would need to depend on some kind of heuristic evaluation of some other kind, no?

furthermore, just detecting the presence of a 3- or 5-way tie (really the only problematic scenarios) seems kinda complicated too. for instance

does a 3 way tie exist between the first, second, and third
or
the 2nd, 3rd, 4th
or
the 3rd, 4th, 5th
etc.

a general solution sounds really complicated.

[mtmosier]

a > b
b > c
c > a

If the above can be true then there really is no way to rank a three way tie. Only ensure that it never happens.

Detecting a three way tie is simple, if not exactly optimal. Just do your normal sort, then loop through with a counter of how many times the current score has appeared so far. But if it's the first three I don't see how that's going to help you.

[sneakyimp]

thanks for helping me think about it.

yeah if you can't really break a three-way tie, it's best to avoid it...or come up with some kind of foolproof tiebreaker sorting function which can always consistently choose one example.

[sneakyimp]

ok...

3 way ties happen in this data. fortunately, i have a foolproof tiebreaker which is decidedly unscientific. i spent about 10 hours yesterday writing and testing an algorithm and it works...i think.

it occurred to me to write a script to try it against every possible test scenario but then i did the math. 75 questions each with two distinct answers means 2⁷⁵ possible tests which means uhhh.....

3.77789E+22 or roughly
37,778,900,000,000,000,000,000 possibilities
did i forget a zero somewhere?

in other words, FOREVER to calculate all the different possible options and test them out. Suppose your computer can analyze one billion possible test scores in a second (not likely). My code is about 350 lines and not quite finished yet. Even at a billion possibilities per second, it would take 37,778,900,000,000 seconds, or 11,971.4 centuries, to analyze all the possibilities. Have I been sloppy with the math? Not every line of my algorithm will get executed every time, but even if i'm off by a factor of 1000, we're still talking about 1100 years.

so anyways. i can only hope my algorithm works. I've tried it on some screwy data....managed to get a 5-way tie pretty easily. it does evaluate the tie somewhat unscientifically but effectively.

[mtmosier]

Nothing saying you have to test all 3.77789E+22 possible outcomes. You could randomly generate ten thousand entries and run that through. You won't be 100% certain, but it's better than nothing.

I'm sure you're aware that line count doesn't equate to speed.

[sneakyimp]

good recommendation. i've already looked inside the scoring and given data that forces some of the more apocalyptic ranking situations and i think that it will work in every case.

testing for 10,000 cases sounds smart too....although that's what? roughly 3e-17 percent? i reckon i should anyway.

thanks for the advice.