[Haskell-cafe] Re: combinatorial search with running bound
mpm at alumni.caltech.edu
Tue Sep 29 00:09:32 EDT 2009
When you ask for a pair of boxes, "How closely can they be brought together
without intersection?" that provides a lower bound on the question "How
closely can the groups be brought together?" (I.e. for that pair of boxes,
bring them any closer and they intersect, so it is a lower bound.) The
maximum of all these lower bounds in the minimum needed separation.
Chung-chieh Shan wrote:
> Michael Mossey <mpm at alumni.caltech.edu> wrote in article <39126.96.36.199.130.1253997756.squirrel at mail.alumni.caltech.edu> in gmane.comp.lang.haskell.cafe:
>> The problem is to determine how closely the groups can be brought together
>> without any boxes intersection.
>> The basic algorithm is to consider each pair of boxes and ask if they
>> have any "vertical overlap"---if so, figure out how closely they can be
>> brought together without intersecting, otherwise ignore them. Then take
>> the maximum of those numbers.
> Wouldn't you mean minimum instead of maximum then?
> I suspect that your code would be clearer without using a state monad.
More information about the Haskell-Cafe