Re: List partitioning

bim wrote:
....
Sorry if didn't go too far in my explanations, but I didn't want it to look like I want someone to do the job for me :/

I am indeed not promising anything, otoh feel like putting the problem in a back burner, but then there is the most relevant piece of data missing : typical values and bounds on the scale of problem cases.

....
Yes but these groups aren't independant. I understand I have more chances to find a better solution in a given time using this method, however I can't be sure it is the best solution unless I try all of them , and then I don't see the benefit of this method (it's very rare to
find a solution where both Dispersion=0 and Balance=0, which is the only case where I know I have a best solution).

Right. Ok, but there should still be ways to minimize computation by working on partial solutions. For instance, you are right in saying that comparison of single possible groups can't ever simply generalize to complete solutions - since two complete solutions that differ by one group do in fact differ by at least two groups. But this suggests it might be worth the while to consider the space of unions of n>1 groups, whose optimization (ie splitting into n specific groups), can be achieved independently of that of their complement set.

Although I never tried it, if you go that route I would suggest trying tabled predicates as is provided by XSB and B-prolog, with the vague idea that they could permit to write the search as a relatively simple-minded systematic computation, leaving to the system the task of recognizing and skipping a repeated sub-computation (to the point of changing the asymptotic behavior).

Cheers, BB
.