Re: List partitioning

bim wrote:
[...]
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...

Mhh, please forgive me, I'll indulge in stating a few opinions...

Python's strength is that it is much more general-purpose, full-featured, and well interfaced to both OS services and all sorts of libraries written in yet other languages - while it does provide some support for doing searches as I've shown. So if your problem here is just a subproblem of a larger programming problem, Python would be a better choice, although this is mitigated by your need to learn it (very easy from an imperative languages background). Python is just very practical for almost everything.

Prolog otoh is beautiful and finding a problem that fits it (note I am saying the problem fits Prolog rather than the other way around) - finding such a problem is rare enough in real programmer life, that the fun opportunity to apply Prolog should not be dismissed lightly, IMO.

There is an issue, though, with the way the built-in search strategy of Prolog guides your intuition to slice search problems in certain manners rather than others. Even if you may end up with splendid solutions after considerable backtracking *in program design*. Generally speaking, I don't believe it is possible to achieve efficient solutions to complex search problems in Prolog without escaping the illusion Prolog invites (and CLP even more), that it is sufficient to consider only the logical semantics and that the operational semantics can be ignored. The fun and beauty of Prolog, IMO, is precisely the other way around, in clothing a well-understood operational semantics (ie the search dynamics) with the apparent simplicity of a limpid logical semantics : but the benefit of this is more artful pleasure than technical ease or particular usefulness.


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

[snip]

I am sorry but I've already diverted too much time away for this, from more pressing tasks. A few remarks, though :

- 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.

- But my tendency whatever the programming language, would be to first seek the most efficient algorithms that use only generate and test over a well thought out partial solutions construction mechanism, and let CLP enter the scene, only if that reveals not to be efficient enough.

- You mention heuristics : this implies fine control over search deepening, where Prolog's built-in search strategy tends to get in the way rather than help (although maybe you can find some library to deal with the complexity).

- Your problem statement isn't wholly crystal-clear, eg the role of +Sizes and the relationship of "item Size" to "group Size" and "group Weight"; but never mind since I don't intend to work on it.

- 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).

Cheers, BB

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
.

Relevant Pages

  • Re: List partitioning
    ... However, now that I'm really used to coding in Perl, I feel less motivation for learning another interpreted language (note that I don't think Perl is better, since I don't even know Python enough to be able to compare them). ... I failed at explaining that but that's what I meant, and that's why I though Prolog would be more suitable. ... I felt this even with the little Prolog program I just did (had to refactor the internal variables structure just in order to apply the constraints "efficiently"...). ...
    (comp.lang.prolog)
  • Re: CLP(FD) team for the ASP solver competition
    ... unquoted variables. ... Prolog is untyped, so why shouldn't we have the luxury? ... equality and several other constraints while many others maintain some ... B-Prolog Version 7.2, All rights reserved, Afany Software 1994-2009. ...
    (comp.lang.prolog)
  • Re: pushing parallel and constraint programming
    ... with constraints. ... Maybe you should look into deductive databases where the ... OntoBroker, smodels, etc.) and there are also Prolog systems that are ... there are a lot of papers by the XSB developers ...
    (comp.lang.prolog)
  • Re: pushing parallel and constraint programming
    ... with constraints. ... Maybe you should look into deductive databases where the ... OntoBroker, smodels, etc.) and there are also Prolog systems that are ... there are a lot of papers by the XSB developers ...
    (comp.lang.prolog)
  • Re: How can I do this without cuts?
    ... > tradeoffs and of integration with other computational models (tabling, constraints, ... > that the Mercury experience is a major improvement in the field. ... Prolog part-application into the application as a whole. ... then we can use Prolog in industry. ...
    (comp.lang.prolog)