开发者

How to check constraints between elements in a list / is this Constraint Programming?

I have many variable-sized lists containing instances of the same class with attribute foo, and for every list I must apply rules like:

  • if there's an element foo=A there cannot be elements with foo in [B,C,D]
  • if ther开发者_开发问答e's an element foo=X there must by at least one with foo in [Y,Z]
  • there can be between MIN and MAX elements foo=BAR

combining the above three rules is probably enough to express any similar constraint I'll ever need. It's something like dependency checking in software packages but I have quantities and lack versions :)

a naïve approach would be:

R_CONFLICT={ A: [B,C,D] }
R_DEPENDS ={ X: [ [Y,Z], W, .. } # means: A depends on either Y or Z, and W
R_MIN     ={BAR: n, BAZ: m}
R_MAX     ={BAR: o, BAZ: p}
# now just loop over lists to check them..

Is this a problem of Constraint programming? I don't actually need to solve something to get a result, I need to validate my list against some constraints and check if they are satisfied or not. How would you classify this problem and how would you solve it?

For what it's worth, I'm coding in Python, but I welcome a generic programming answer :) If it turns out I must delve in constraint programming I'll probably start by trying python-constraint.


Short answer - yes this could be checked using constraint programming, in effect you are supplying a solution and checking it against constraints rather than having the solver search through domains of potentials for a matching solution. Which kind of makes constraint programming overkill, especially if you are using Python which can quite easily check those kind of conditions.

I don't have Python on this machine so there may be a typo/error in this code but it shows what you're after without needing to get involved with constraint programming.

conflict = set([B, C , D])
foos = set([x.foo for x in list])
if A in foos:
    if len(foos & conflict): #Set intersection
         return false

len([x for x in list where x.foo == BAR]) #Gives you number of occurances of BAR

Basically I'd say unless the constraints are going to get much more complex or you're going to want to find solutions rather than just test I'd stick with code rather than constraint programming.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜