Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1390
  • Posts: 23442
October 11th, 2010 at 4:44:57 PM permalink
I saw the movie The Social Network about a week ago. It was quite good, I might add. As those who saw the movie will know, while still a Harvard student, Facebook creator Mark Zuckerberg created a site in which he posted pairs of pictures of female Harvard students and asked student to rank which one was more attractive. The object, I think, was to give each girl a rating, as judged by the users of the site.

It got me to thinking. Suppose you had a x such pictures, and wished to sort them in attractiveness order yourself. What would be the most efficient strategy? You are limited to comparing two pictures at a time. I'm open to how "efficient" should be defined, but I would suggest minimizing either expected matches required, or maximum matches.

I'll hold off on posting my strategy for the moment. However the following table will show the minimum and maximum number of pairings it would produce.

Faces Min matches Max matches
2 1 1
4 5 5
8 15 20
16 49 76
32 169 288
64 609 1104
128 2273 4288
256 8705 16832
512 33921 66560
1024 133633 264448
2048 529921 1053696
4096 2109441 4205568
8192 8415233 16801792
16384 33611777 67162112
It's not whether you win or lose; it's whether or not you had a good bet.
Doc
Doc
Joined: Feb 27, 2010
  • Threads: 45
  • Posts: 7107
October 11th, 2010 at 5:01:38 PM permalink
I would expect that in this type of subjective ranking/sorting, the issue of consistency would be more problematic than the issue of efficiency. By this I mean that if I rank A higher than B and B higher than C, I am still not certain that I would necessarily rank A higher than C in a direct comparison.

Edit: Or that I would necessarily rank A higher than B if I repeated the comparison.
larwiz1
larwiz1
Joined: Sep 16, 2010
  • Threads: 15
  • Posts: 58
October 11th, 2010 at 5:38:50 PM permalink
I may not understand what is required, but looking at your table.

Suppose we have 3 (A,B,C)-I would compare AB and put them in order. I would then compare C to the best (most attractive), assuming it was A, if C is more attractive then I would have my minimum matches (2), with CAB order, if C was not more attractive then I would compare CB an put them in order for a max match number of 3.

Now for four (A,B,C,D). I would take the same strategy. Compare AB, put them in order and compare C to the best (assume A), if C most attractive, then my order is CAB (at this point), I then would compare D to C, If D more attactive my work is done with a minimum 3 matches and a DCAB order. If D is not more attractive I would compare D to A, if more attractive then my work is done (4 matches), with an order of CDAB, if not then a 5th match will determine the DB order.

I would do the same strategy with more faces. It seems it is possible that the minimum could be the number of faces minus 1, however improbable.
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
October 11th, 2010 at 7:32:30 PM permalink
Quote: Wizard


It got me to thinking. Suppose you had a x such pictures, and wished to sort them in attractiveness order yourself. What would be the most efficient strategy? You are limited to comparing two pictures at a time. I'm open to how "efficient" should be defined, but I would suggest minimizing either expected matches required, or maximum matches.



You're asking about sorting algorithms and computational complexity, two fundamental topics in computer science. Start here:

http://en.wikipedia.org/wiki/Sorting_algorithm

"Efficiency" depends on several factors like whether you care more about runtime or storage space, or what you know about your data (e.g. is it nearly-sorted or very out-of-order).

More info: the presumption in your question is that you have a collection of N objects and a binary-comparison function f(a, b) which returns >0 if a > b, 0 if a == b, and <0 if a < b. If you don't have that, for example you sometimes rank a > b and other times a < b (entirely possible when dealing with "attractiveness"), then it's a different problem that doesn't map well to existing algorithms.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
FinsRule
FinsRule
Joined: Dec 23, 2009
  • Threads: 123
  • Posts: 3773
October 11th, 2010 at 7:50:57 PM permalink
This is only slightly related to the original question, but, I believe that attractiveness is normally distributed. If average attractiveness is a 5 out of 10, I believe the standard deviation is 1.5. I think 95% of people fall into the 2-8 category. Meaning that only 1 in 40 women would really be considered a 9 or a 10.

My wife asked me what she was. I told her that of course she's a 10.
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1390
  • Posts: 23442
October 11th, 2010 at 8:22:27 PM permalink
Quote: MathExtremist

You're asking about sorting algorithms and computational complexity, two fundamental topics in computer science. Start here:

http://en.wikipedia.org/wiki/Sorting_algorithm...



Thanks, good answer. I was trying to do something like a merge sort, but my method was not optimal. I'll need some more time, but hope to answer my own question tomorrow.
It's not whether you win or lose; it's whether or not you had a good bet.
Doc
Doc
Joined: Feb 27, 2010
  • Threads: 45
  • Posts: 7107
October 11th, 2010 at 8:36:55 PM permalink
Quote: MathExtremist

... the presumption in your question is that you have a collection of N objects and a binary-comparison function f(a, b) which returns >0 if a > b, 0 if a == b, and <0 if a < b. If you don't have that, for example you sometimes rank a > b and other times a < b (entirely possible when dealing with "attractiveness"), then it's a different problem that doesn't map well to existing algorithms.

Hmmm. I think that just might be the mathematician's way of saying what I tried to convey about the issue of consistency in my earlier post. Or did I misunderstand once again?
mkl654321
mkl654321
Joined: Aug 8, 2010
  • Threads: 65
  • Posts: 3412
October 11th, 2010 at 9:23:46 PM permalink
This seems so obvious to me. And I can do it without getting all mathy:

Take two pictures. Rank them in order of attractiveness.

Take the third picture, and compare it to the bottom picture. If Pic 3 is lower in attractiveness than the bottom picture, put it at the bottom. If higher, compare it to the top picture, and place Pic 3 either in the middle or above the top picture, according to the results of the comparison. You now have three pictures in ranked order.

Take Pic 4 and compare it to the middle picture. This will tell you whether to move it up or down. In each case, compare it to the next picture in the relevant direction, and use that comparison to place Pic 4 either between the middle and that pic, or at the top or bottom. You now have four ranked pics.

Repeat this procedure with each successive pic, starting as close to the middle as possible. If a given comparison preserves the existing position of the new pic, leave that pic there. For example:

Seven pics have been ranked. Take Pic 8 and compare it to the fourth-ranked pic. If it is more attractive, compare it to the third-ranked pic. Repeat until the pic stops moving up, then place the pic in that position. Same procedure if the initial comparison shows the new pic to be less attractive than the middle pic; keep moving down until it stops, then place the new pic in that position.

No math necessary.
The fact that a believer is happier than a skeptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality.---George Bernard Shaw
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1390
  • Posts: 23442
October 11th, 2010 at 10:00:52 PM permalink
Quote: mkl654321

This seems so obvious to me. And I can do it without getting all mathy...



That is an acceptable way to do it. It would be more efficient than the standard bubble sort. However, the question is can you prove it minimizes the expected or maximum number of comparisons?
It's not whether you win or lose; it's whether or not you had a good bet.
mkl654321
mkl654321
Joined: Aug 8, 2010
  • Threads: 65
  • Posts: 3412
October 11th, 2010 at 10:39:44 PM permalink
Quote: Wizard

That is an acceptable way to do it. It would be more efficient than the standard bubble sort. However, the question is can you prove it minimizes the expected or maximum number of comparisons?



Not mathematically, but it would seem that making each new placement by comparing that picture with the current middle-ranking picture, and then moving up or down as needed, would minimize the number of comparisons, as any new entrant is most likely to wind up as near the middle of the existing group as possible (if there are eight existing ranked pictures, the new picture would be more likely to wind up #5 in the resultant group of nine than in any other position).

To put it another way, a comparison with the middle of the existing group gives the most information; comparing a new entrant with the top or the bottom ranking picture gives minimum information; so the optimal comparison method is to start in the middle.
The fact that a believer is happier than a skeptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality.---George Bernard Shaw

  • Jump to: