0

I am trying to come up with a algorithm for the following problem.

There is a set of N objects with M different variations of each object. The goal is to find which variation is the best for each object based on feedback from different users.

At the end, the users will be placed in a category to determine which category prefers which variation.

It is required that at most two variations of an object are placed side by side.

The problem with this is that if M is large then the number of possible combinations become too large and the user may become disinterested and potentially skew the results.

The Elo algorithm/score can be used once I know the order of selection from the user as discussed in this this post Comparison-based ranking algorithm

Question:

Is there an algorithm that can reduce the number of possible combinations presented to a user and still get correct order?

example: 7 different types of fruits. Each fruit is available in 5 different shapes. The users give their ranking of 1-5 for each fruit based on the size they prefer. This means that for each fruit there are max 10 combinations the user has to choose from (since sizes are different, no point presenting as {1,1}). How would I reduce "10 combinations" ?

Community
  • 1
  • 1
Varun Dave
  • 179
  • 1
  • 2
  • 12

1 Answers1

0

If the user's preferences are always consistent with a total order, and you can change comparisons to take account of the results of comparisons made so far, you just need an efficient sorting algorithm. For 5 items it seems that you need a minimum of 7 comparisons - see Sorting 5 elements with minimum element comparison. You could also look at http://en.wikipedia.org/wiki/Sorting_network.

In general, when you are trying to produce some sort of experimental design, you will often find that making random comparisons, although not optimum, isn't too far away from the best possible answer.

Community
  • 1
  • 1
mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • I don't quite follow what you mean by consistent with a total order. Can you explain please? – Varun Dave Sep 14 '12 at 18:32
  • If the user prefers A to B, B to C, and C to A, then a clever sorting algorithm might deduce incorrectly from the first two preferences that the user prefers A to C. This sounds bizarre, but can happen for a host of reasons - for an amusing one see http://en.wikipedia.org/wiki/Nontransitive_dice. – mcdowella Sep 14 '12 at 19:11