Roleplaying Video Games Entertainment & Media Politics & Religion General
Worldbuilding Creative Forum The Sports Center Science, Math, & Technology The Nostalgia Forum
GTX0 is community-run. Do you have an issue or suggestion? add_comment Add one

Science, Math, & Technology

rankingsorting a list by choosing between two or more repeatedly

Posted 6 Months ago by mariomguy

When playing Mario Kart 8 online, I get a choice between 3 courses. Over time I realized there was a certain rank to my favorite and least favorite courses based on which one I selected by comparing only 2 or 3 at a time.

So, I'm looking for a solution to create a ranked list based off of repeated votes between 2 or more choices.

I've looked into various sorting lists and there are some I seem to understand more than others, but all of them seem to have the issue of recursion: if you like option 1 better than 2, and 2 better than 3, then most algorithms assume you like option 1 better than 3.

I created my own from scratch like tournament scoring and ranked 1-8 choices, but not successfully. Anyone who loses the first round immediately gets put in the loser's bracket, and there's no way to succeed more than the bottom half after that. I've yet to figure out a mathematical solution other than simply a function to replace the top victors. This list secures the 1st, 7th, and 8th. places properly, but with poorer quality results in the middle.

There are 14 Replies


I've looked into various sorting lists and there are some I seem to understand more than others, but all of them seem to have the issue of recursion: if you like option 1 better than 2, and 2 better than 3, then most algorithms assume you like option 1 better than 3.


If there is one dimension to "liking something" and that dimension is quantifiable, then yes, (A > B) & (B > C) = (A > C). In terms of ranking works of art with all of the extreme variety of qualities thereof, and various disciplines and ideologies of analyzing and critiquing those qualities, trying to boil it down to a simple flowchart or rating is, to put it lightly, a contentious subject.

6 Months ago
Canary Yellow
 

If I'm understanding you right, you want to rank a list of items by comparing each item to every other item. So the way to do that is to:

  • Have a tally for each item.

  • Compare every item to every other item. Whichever item wins, give it a +1 tally.

  • Compare the tallies at the end -- whichever one has the most tallies is your favorite, and then the other items are ranked by the total amount of tallies they have.

    So for example, if the options are "favorite colors" and the choices are Red, Green, Blue and Yellow:

    Color Is better than Is worse than
    Red Green, Blue Yellow
    Green Yellow Red, Blue
    Blue Green Red, Yellow
    Yellow Red, Blue Green


    In this particular example, you like Red better than Green, and you like Green better than Yellow, however you like Yellow better than Red.

    Despite you liking green more than you like yellow, yellow actually has a higher rank than green because you like it better than both Red and Blue, whereas with Green you only like it better than yellow.

    Is that what you're going for here?

  • 6 Months ago
    Riven
     

    Or just do what Xhin said, because he obviously has a better handle on this than I do. It's been a long time since I've taken a logic class.

    6 Months ago
    Canary Yellow
     

    Here's a little javascript application I made that does exactly what I outlined above -- stick your entries on new lines, pick what you like better between each set, and it'll calculate your favorites for you:
    http://gtx0.com/projects/ranking/

    6 Months ago
    Riven
     

    ...Well, that was easy. Just compare everything to every other thing and tally the points. That's the only way to do it right.

    But what's harder, if we assume the > recursive logic is OK, then how can we compare, like, 32 entries without needing over a thousand votes to make a list? What if we only had, like, 50 votes?

    6 Months ago
    mariomguy
     

    Here's what I want to do: I want to have a list of movies, or games, throw a whole bunch in a list, and make some votes on which is better. Then I want the rest of the list to populate without me needing to make so many votes. The more votes the more accurate the list will be, but the list can assume everything else based on the progression of 3 > 2 > 1, therefore 3 > 1.

    I want to do this with like, literally everything.

    6 Months ago
    mariomguy
     

    If the recursive logic is okay, then you can find your favorite of 32 entries with as few as five questions:

  • 1. Put 16 on one side and 16 on the other. Decide which side you think is better.

  • 2. Take that side and split it so 8 are on one side and 8 on the other. Do the same thing.

  • 3. Repeat this with 4 on each side.

    4. 2 on each side.

    5. Rank the last two entries against each other.

    If you can't reasonably compare 16 entries with 16 other entries at once, you can alter that step so that you have four groups of 8. You then pair these groups off and then pair the winners to get the winning group of 8 -- so it takes 3 comparisons in all for that step.

    Every time you split a group down into more manageable chunks, you add the next power of 2 to the total number of weighings. If weighing 8 against 8 isn't manageable, you're already at 2^0 (1) + 2^1 (2) = 3, so you add 2^2 (4) extra turns to downshift into 8 groups of 4.

  • 6 Months ago
    Riven
     

    I think I'm misunderstanding what you're trying to do exactly -- can you give an example?

    6 Months ago
    Riven
     

    So, let's use a small number, power of 2, to make things easier: 4. I want to rank 4 things in order from best to worst accurately by only voting for 2 at a time, x number of times. I want to have an accurate list with the fewest x votes.

    Consider the insertion method.

    Grapes
    Watermelons
    Apples
    Bananas

    First vote will be Grapes vs. Watermelon, I like Grapes. Second is Grapes vs. Apples, I still prefer Grapes. Third vote is Grapes vs. Bananas, I still prefer grapes. So the simple sort puts Grapes on top, but I need more votes between Watermelons, Apples, and Bananas: I like Watermelons more than both (2 votes, 5 total), and Bananas more than Apples (6 votes total).

    After just 6 AB votes, we can sort these 4 entries into a pretty clear ranking from first to last.

    6 Months ago
    mariomguy
     

    Right, that's what my first post (and tool) did.

    The longer your list, the more votes you have to do -- if e is your number of entries, then you need to inclusively add every number between 1 and (e-1) to figure out how many votes you need for an accurate result.

    Putting this into gauss's formula, you end up with ( e(e-1) ) / 2.

    So for 8 entries for example, to get an accurate list you need 1+2+3+4+5+6+7 votes, or
    ( 8(8-1) )/2, which is 28.

    For 64 entries, you end up needing 2016 votes, as opposed to the "recursive" bracket system where you only need e-1 votes, so 63.

    6 Months ago
    Riven
     

    Your list actually did solve the problem perfectly. That was incredibly fast... holy crap.

    This makes me want to learn Javascript. But C++ would be more useful in UE4.

    6 Months ago
    mariomguy
     

    Your list actually did solve the problem perfectly. That was incredibly fast... holy crap.


    All it does is replicates my post above.

    Shatterloop is entirely written in javascript so my skills there are pretty strong.

    This makes me want to learn Javascript. But C++ would be more useful in UE4.


    It doesn't really matter which language you learn, the skills will transfer over to other ones. Do enough C++ and you'll be able to do stupidly complex things in javascript too (once you figure out its quirks of course).

    6 Months ago
    Riven
     

    If I am not mistaken the average number of comparisons you need to make is approximately n*(log(n)/log(2)) at a minimum if you can assume transitivity?
    And averages something proportional to that even if your algorithm is not as efficient as possible (as it usually can’t be)?

    (Of course if they’re already in order the most efficient algorithms need only n-1 comparisons, if you can assume transitivity.)

    So 1 comparison for 2 entries (duh!)
    8 comparisons for 4 entries (overestimate; least efficient algorithm needs only n(n-1)/2 = 6 comparisons)
    24 comparisons for 8 entries (fewer than 8*7/2 = 28)
    64 comparisons for 16 entries (a lot fewer than 16*15/2 = 120)
    160 comparisons for 32 entries (way fewer than 32*31/2 = 496)
    and so on.
    It partly depends on luck; what order are they already in?
    If you can make any assumptions about the order they’re already in, you can select an algorithm that will take advantage of that.


    —————

    If you can’t assume transitivity, the problem is essentially equivalent to the problem of deciding the order-of-finish in a multi-candidate election with ranked-voting.

    4 Months ago
    chiarizio
     

    I forgot to tag anybody in my post I just made.

    4 Months ago
    chiarizio
     

    Reply to: rankingsorting a list by choosing between two or more repeatedly

    Username
    Password