Help! Logical calculation of pair comparisons from analysis of existing results

ivehadanidea

Apologies if this has been asnswered before or if it's in the wrong place but I really don't know the proper terms I should be looking for.

I have a system whereby people are asked to choose between two items, then another two, etc. until all paired combinations from the list of items has been tested. This gives me a ranking order.

e.g. we have 3 items; A, B and C.
Each item must compared against each of the others, which may give us this result:

A > B
B > C
A > C

By '>' I mean 'better than', as in an opinion, rather than 'greater than', as in a mathematical fact.

My problem is this:

I want to be able to automatically calculate any possible results without having to ask them to the user. In the above example we only need have asked 2 comparisons, since by the third we knew A > C since A > B > C. It was ok to ask all possible combinations here as there are only 3 but in my real situation I will have at least 5 items, which means 10 possible combinations.

How can I apply this logic to minimise the number of questions I need to ask before I know the result of each combination?

I will be programming this in SQL since the results are coming from a database. Any help with that in mind would also be much appreciated.

Thanks in advance!

matt grime

It's called sorting. There was a whole book written about it by Knuth. There are many algorithms: quicksort, bubblesort, mergesort, to name just 3.

I'm sure now you have the right area to search for you will find the method that suits best (some need more memory, others more time, etc).

Incidentally, your example above didn't need just 2 comparisons. You only say that because you got A>B, and then B>C. Suppose that the second test gave you C > B instead. Now you have no way to know if A>C or C>A without a 3rd test. There is a difference between expected time and worst case time in the different algorithms.

ivehadanidea

Thanks Matt,

I realise that if the second result had been C > A then a third comparison would have been required. This is exactly why I need to find an algorithm that I can run each time a comparison is made, so that after every answer I can fill in any possible blanks and move on to the next question deemed necessary to ask.

This is great, thanks for pointing me in the right direction, I'll be looking into sorting to see if I can find an approriate solution.

matt grime

I just noticed that you didn't mean > to mean any technical notion of order. You may well find that if you're attempting to use something subjective (someone's opinion of something) you will find that people are not consistent in their choices.

You may also wish to read about reconstructing partial orders (as opposed to well orders) and the secretary problem.