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 |

Edit: Or that I would necessarily rank A higher than B if I repeated the comparison.

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.

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.

My wife asked me what she was. I told her that of course she's a 10.

Quote:MathExtremistYou'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.

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

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.

Quote:mkl654321This 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?

Quote:WizardThat 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.