?>
Happy 11th birthday, gtx0!


Ranking/Sorting a List by Choosing Between Two (or More) Repeatedly
Posted: Posted August 8th by mariomguy
View Source Report Thread Views

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
Load all posts On page: 1 2
  settingsSettings

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.

Posted August 8th by Canary Yellow
View Source Quote Report

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?

  • Posted August 8th by Xhin
    View Source Quote Report
    Xhin
     

    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.

    Posted August 8th by Canary Yellow
    View Source Quote Report

    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/

    Posted August 8th by Xhin
    View Source Quote Report
    Xhin
     

    ...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?

    Posted August 8th by mariomguy
    View Source Quote Report

    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.

    Posted August 8th by mariomguy
    View Source Quote Report

    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.

  • Posted August 8th by Xhin
    View Source Quote Report
    Xhin
     

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

    Posted August 8th by Xhin
    View Source Quote Report
    Xhin
     

    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.

    Posted August 8th by mariomguy
    View Source Quote Report

    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.

    Edited August 9th by Xhin
    View Source Quote Report
    Xhin
     
    Next page Load rest of pages On page: /
    Reply to: Ranking/Sorting a List by Choosing Between Two (or More) Repeatedly
    Enter your message here

    Rules | Report Issue | Request Feature | Roadmap Facebook Page | Discord Group
    GTX0 © 2009-2020 Xhin GameTalk © 1999-2008 lives on
    You are not forgotten, Kevin, Liane, Norma, Jason, and Garrett