Re: List partitioning

Boris Borcic a écrit :
bim wrote:
Good you say this, makes your problem sound less like homework (since what need would you have for an complete list of possible partitions rather than just one ?).

Actually I though I shouldn't explain the entire problem at start because it would make people go away :/
And at that time I was just trying to improve the main research algorithm (I was having hard time remembering Prolog basics ;) ).

This said - and while I don't mean to argue against Prolog (I am a lurker here for *some* reason) - I do not see that your conclusion follows clearly (that Prolog is a better fit). Witness that the most concise solutions provided in both languages to your initial simplified problem, have *exactly* the same syntactic complexity - what gives no reason to think that solutions to the complete problem would be different.

Well, the fact that I'm looking for the best solution based on heuristics and constraints made me think Prolog was the best choice. However, I almost don't know anything about Python, so maybe you're right, maybe Python is as good as/better than Prolog for my problem...

For information, here is the entire problem I'm trying to solve:

Initial data:
------------
- N items
- Each item has a weight and a size
- Some items are already grouped

What I want:
-----------
- P groups of items (each group must have the same size, or only differ by 1 from the other if it isn't possible)
- minimize the differences between all groups weight
- if the solution isn't good enough (not balanced enough), then break the initial groups (just the minimum needed)

I've made a Prolog code that does what I want, except it takes too much time (I think it's possible to do much better):


balance(+Weights,+Sizes,+PreGroups,+NbGroups,-Assignations,-BalanceHeuristic,-DispersionHeuristic)
+Weights: list of item's weights
+Sizes: list of item's sizes
+PreGroups: groups of items that we should avoid breaking
+NbGroups: number of item groups we must create
-Assignations: the assignation of each item to a group
-BalanceHeuristic: sum of the groups weights deviation from the mean group weight
-DispersionHeuristic: sum of the initial groups (PreGroups) broken by each team


example:

?- statistics(cputime,Cpu1),
balance([12,23,10,23,34,33,15,24,30,11,15,19,30,20,33,23],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[[1,5,6],[3,10]],
2,
[P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12,P13,P14,P15,P16],
Bal,
Dis),
labeling([min(Bal),min(Dis)],
[P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12,P13,P14,P15,P16]),
statistics(cputime,Cpu2),
Cpu is Cpu2 - Cpu1.
Cpu1 = 0.04,
P1 = 1,
P2 = 1,
P3 = 1,
P4 = 2,
P5 = 1,
P6 = 1,
P7 = 2,
P8 = 1,
P9 = 1,
P10 = 1,
P11 = 2,
P12 = 2,
P13 = 2,
P14 = 2,
P15 = 2,
P16 = 2,
Bal = 1,
Dis = 0,
Cpu2 = 6.66,
Cpu = 6.62
.