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, 2012 at 3:52
  • $\begingroup$ What do you mean by better? Just faster, or something else? $\endgroup$
    – David Ketcheson
    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$
    – Gareth A. Lloyd
    Jan 21, 2012 at 14:44
  • $\begingroup$ @Dan I'll look into using that. $\endgroup$
    – Gareth A. Lloyd
    Jan 21, 2012 at 14:44

0

Reset to default

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.