From: Robert Klemme <bob.news@...>
Date: 2004-10-10T22:54:40+09:00
Subject: Re: Unofficial quiz: Here's an algorithmic question for you


"Mauricio Fern�ndez" <batsman.geo@yahoo.com> schrieb im Newsbeitrag 
news:20041009235149.GA10987@student.ei.uni-stuttgart.de...
>> So my real questions are:
>>
>> 1. How would you solve the problem of evaluating the correctness
>>    of the partitioning? This would have to be "fuzzy" in some
>>    sense, of course -- maybe a Float answer between 0 and 1.
>
> mmm what about the following:
>
> Define a mapping from elements in your working set to a feature vector.
> Compute the average feature vector for each of A={a,...,d} and 
> B={e,...,h},
> note them V_i and W_j (for i,j=1..4)
> then you can define a distance as the minimum of
>  sum(|V_i-W_a(i)|^2, i=1..4)   with a(i) representing the association
>                                between averages in A and B
> (there are 24 such mappings)

That's interesting.  I took a bit less formal mathematical approach of 
thinking, but I think the solution is quite similar.  Here's what I'd have 
done: for all permutations of e,f,g,h divide the size of the set 
intersection of each pair by 25 (the set size) and then compute the average 
of these values for all four pairs.  Now choose the permutation of e,f,g,h 
with the highest value.

As the faculty function is involved for a general solution there could be 
numerous optimizaions.  For example, it is reasonable to first calculate the 
match indicators (intersection size / set size) for all pairs with O(n^2), 
order the result buckets per original bucket with decreasing match indicator 
and use that to guide the permutation.  If you're lucky (i.e. if the bucket 
finding algorithm worked well) every original bucket has a different 
calculated bucket as first element in the ordered list and you're done 
immediately.

If not, it's more difficult if you want to find the optimal permutation.  If 
you just want to detect failure of the bucket finding algorithm it might as 
well suffice to recognize that two of the original buckets have the same 
best match calculated bucket (which then both must have a match indicator <= 
0.5 which seems pretty bad IMHO).

Another line of action could be to rule out pairs below a certain match 
indicator (say 0.8) to reduce the number of permutations to consider.

Kind regards

    robert