Re: List partitioning

On 28 oct, 19:22, bim <inva...@xxxxxxxxxx> wrote:
Boris Borcic a écrit :
....
- In my sense, what you mean to apply is not just Prolog, but CLP. Now
if your problem really requires constraint propagation to achieve
efficiency as the case may be, Python isn't competitive with specialized
languages.

Exactly.

But what I meant is that CLP being /required/ isn't obvious before
really trying to do without.
Besides I was a bit fast saying that Python did not compete : the
python package index lists a python constraint satisfaction library at
http://www.logilab.org/project/logilab-constraint/

....
- For a strategy, it appears that the relative value of a complete
solution (partition) might be expressed as the sum of the (eg stable)
relative value of each component set (or some slightly relaxed property
equivalent for the purpose). This suggests you should first generate
(possibly lazily (...heuristics)) a sequence of component sets ordered
by decreasing value, and then from that list, eagerly pick candidate
components to incrementally construct a complete solution (much like
nCombis is used in partEvenly() of my initial Python program).

I'm not sure to get exactly what you mean right now, given that I have
two values assigned to each solution (Balance and Dispersion), and that
I need first to get the solution with {min(Dispersion) and
min(Balance)],

How are they defined (well I gather one is related to "Size" and the
other to "Weight") and more importantly what does "and" mean if the
two minimizations conflict ? Is it a lexicographical ordering, ie
min(Dispersion) and for the same value of Dispersion, min(Balance) ?

What I mean is that possibly the implied preferability ordering over
complete solutions to a particular problem case, is such that it
implies in turn a preferability ordering over all possible component
sets aka "individual groups" *independently* of their being assembled
in this or that complete solution, from what the best complete
solution(s) could then be constructed by taking the groups in (their
own) preferability order and adding them to the (initially empty)
partial solution whenever they are compatible with it.

And then, possibly this is not quite the case but near enough that an
adaptation of this approach would be efficient.

In your case, isn't Dispersion measured as the sum over component
groups, of the difference of the group's size to the average size
(which is fixed for a problem case), and Balance samewise while
exchanging weight for size ? In that case, if it happens say that the
aggregate desirability of the complete solution can be expressed as a
linear function of both Dispersion and Balance, this value can be
viewed as the sum of a contribution by each group that does not depend
on that group being considered in the context of a particular
partition.

Cheers, BB

.

Relevant Pages