1
$\begingroup$

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
  else:
    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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.