CODEWITHSUNDEEP
algorithmlogic
Julian Gold
Julian Gold

Reputation: 1286

Algorithm for necessary / sufficient conditions

I have a set of conditions each of which can be one of Optional, Necessary or Sufficient. Clearly the set is met if any of the sufficients are true. And if all of the necessaries are true. (Optionals are irrelevant).

But obviously this simplifies because if I find any sufficient condition is true, I don't need to keep on looking (it's met). And if any of the necessaries are false, then the set can't be met. So in pseudo-code

for(condition c in conditions) {
    if condition.Necessary:
        if !condition.evaluate() return false
    else if condition.Sufficient
        if condition.evaluate() return true
}

return ???

So I'm stuck at the last bit. What's the test at the end? I had simply "must be true" but that breaks with a set of size 1 with a sufficient condition that's not met. Is there a short-cut, or do I need to just evaluate all the conditions and count the cases?

Upvotes: 0

Views: 131

Answers (1)

Levi Ramsey
Levi Ramsey

Reputation: 20561

But obviously this simplifies because if I find any sufficient condition is true, I don't need to keep on looking (it's met). And if any of the necessaries are false, then the set can't be met.

Not necessarily, unless there's an unstated assumption that the set of conditions does not contain a contradiction (e.g. there's a necessary/false and a sufficient/true). Unless you can prove that there's no contradiction, the simplification doesn't actually hold.

If the interpretation is

  • true: any sufficient is true or all necessaries are true
  • false: all sufficients are false or any necessary is false

then (subject to the above note about contradictions)

boolean allNecessariesTrue = false

for (condition c in conditions) {
  if condition.Necessary:
    if !condition.evaluate():
      return false
    else
      allNecessariesTrue = true
  if condition.Sufficient:
    if condition.evaluate() return true

return allNecessariesTrue

Upvotes: 1

Related Questions