All,
I need to determine the furthest distance two selections are from a list of possible selections. The current solution is O(N^2 - N) requiring (N^2 - N) / 2 compares. In other words, comparing every selection in the list against every other selection in the list. My gut tells me there is a better way.

Let's say a selection is a particular outfit. Each category (hat, top, bottom, shoes, etc) has a fixed number of possible choices to choose from. Comparing the selections of two people, the distance will be the number of category items that they chose differently. If they picked the same hat, shoes and pants but a different top then the distance would be 1.

Obviously the maximum distance then is the number of categories. In my case, more than 5 but less than 10. The number of selections will also be fairly small - no more than a dozen. My current approach is to determine the distance for every selection using a high water mark algorithm. Unfortunately, the only opportunity for short circuiting is if two selections have the greatest distance possible.

I want to be clear - there is absolutely nothing wrong with my current solution. I am only seeking wisdom for wisdom's sake. I understand that there can be no better solution in the worst case than what I have already come up with. In my actual data though, most selections will not differ from others by a great amount.

One idea I had was to convert the selection to numbers. Each time a new high water mark is found, only selections that are at least that number away are considered. I haven't worked out a system yet for this.

What ideas do you have?

Cheers - L~R

In reply to Help thinking about an alternate algorithm by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.