2 replies to this topic

[Hoffmann Peter]

Hello, I come directly to my question:

I have a set of objects (not OOP but real objects) with several properties.
I also have a set of rules of which each rule applies to one object and is composed of different conditions that may be satisfied by a property of that object or not.

I now want to get an algorithm that tells me if the set-of-rules fits the set-of-objects or not - for which each object may only fulfill one rule but it is possible that several object-rule-allocations might work for that set-of-rules-set-of-object configuration. I also want to know which object(s) fit which rule.

Detail Problems:
a) If I have two rules of which rule #1 is fit by objects #1 and #3 and and rule #2 is fit by object #3, than obviously the object-rule-allocation should be
rule #1 - object #1 and rule #2 - object #3.
b) Beneath easy conditions that test a string or number against another fixed string or number I want to be able to use conditions that refer to objects that fulfilled another rule, e.g.: Have the same value in property X as the object fulfilling rule #5.
c) I want to be able to not only have several rules but also a rule that is actually a set of rules, e.g.: A rule that may be fulfilled by as many objects as possible that fulfill the conditions, at least 3.

I give you an example (very simple and for sure not sufficient to through think the problem):
The objects may be six Workers in SomeOffice:

Name       | Age | Salary | IQ  | Sex
======================================
Ted        | 31  | 25     |  99 | m
Christine  | 28  | 21     | 105 | f
Mike       | 45  | 40     | 101 | m
April      | 39  | 27     |  89 | f
Tom        | 35  | 30     | 115 | m
Clara      | 37  | 38     | 119 | f

And I have 3 rules:
1) A worker age>25 & salery<35 & IQ> 100 & sex = m
2) A worker age>30 IQ> 100 & sex = f
3) A worker age>30 & salery>25 & Name starts with "T"

Solution:
a) the set-of-rules is fit by this set-of-objects and
b) Rule#1 -> Ted; Rule #2 -> Clara; Rule #3 -> Tom

Another 3 rules:
1) A worker age>25 & salery<35 & IQ> 100 & sex = m
2) A worker age>30 IQ> 100 & sex = f
3) A worker age>30 & salery<30 & Name starts with "T"

Solution:
a) the set-of-rules can not be fit by this set-of-objects (you can not use Ted to fulfill Rule#1 and Rule#3)
b) can not be answered

Please do not stick to this example!


I would be glad to discuss several approaches and please, this is over all a very abstract problem, I'm not looking for code snipplets. I want to thank anybody that took the time and even read this post and try to understand the problem.

[abzero]

The simple problem, solving a) only is quite simple, for each rule find all objects that match, then find each slice of values in the resulting sets to generate your values.

The b&c conditions are a little harder to solve.

[Hoffmann Peter]

I post meta code I constructed in my head:

• Expand every Meta-Rule to the least number of rules it should match (e.g. from one meta rule that must be matched at least 3 times, 3 rules are created)
  
• Create a list of objects that fit a rule (without the related conditions) for every rule
  
• Every object that is the only member of a list is removed from every other list (repeat this process until everthing is clear)
  
• If any list is empty return false
  
• Create a list of all rule-to-object combinations that are possible
  
• For any such combination check if all related conditions are fulfilled, if not delete that combination from the combination list.
  
• If less then one combination is available return false
  
• Fill all meta rules with a 0-oo number of fitting rules for that combination
  
• Decouple the different combinations back into the objects-fulfilling-a-rule list

(Step 2-4 might be omitted)

Any comments on that?