I have a set of constraints over modular domains e.g. $\exists a \in A_i : x \equiv a \pmod{n_i}$ for all $i=0,\ldots,k$

The question is, does such an $x$ exist? I've been pointed to method of successive substitution which ended up with me implementing the following python code.

import fractions
def exist(ruleList, acc = [0,1]): # currentCandidate , currentDomain
  if len(ruleList) == 0:
    return True
    rule = ruleList[0]
    n = rule[1]/fractions.gcd(rule[1], acc[1])
    newDomain = acc[1] * n  
    for candidate in (acc[0] + acc[1] * i for i in xrange(n)): 
      if candidate % rule[1] in rule[0]:
        if exist(ruleList[1:], [candidate, newDomain]):
          return True
    return False

rules = [([0,1,2],5),   # A_1,n_1
         ([4,5,6],9),   # A_2,n_2
         ([0,3,6],10)]  # A_3,n_3

print (exists(rules),)  # True

rules = [([0,2,3],5),   # A_1,n_1
         ([1,2,8],9),   # A_2,n_2
         ([4,6,9],10)]  # A_3,n_3

print (exist(rules),)   # False

Is their a better way of implementing this or better algorithmic approach?

  • 2
    $\begingroup$ This might be interesting to you. $\endgroup$
    – Dan
    Commented Jan 21, 2012 at 3:52
  • $\begingroup$ What do you mean by better? Just faster, or something else? $\endgroup$ Commented Jan 21, 2012 at 12:14
  • $\begingroup$ @DavidKetcheson, better in terms of improving the worst case complexity and/or speed optimisations (reduced memory copying, etc). $\endgroup$ Commented Jan 21, 2012 at 14:44
  • $\begingroup$ @Dan I'll look into using that. $\endgroup$ Commented Jan 21, 2012 at 14:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.