右から2桁の5つの数字から数字Xを派生させてください

Question

0から9999までの5つの数字の入力に基づいて、数値Xを導出する以下のコードを書いています。 Xも持っていますが、その位置は間違っています（例えば、1000位のXの数字は100桁で与えられます）。

例入力：

6087,5173,1358,3825,2531 

この入力に対して期待出力される。

8712 

以下のコードは、Xを算出し、それは強引です。どうすれば時間の複雑さを減らすことができますか？

m = ('6087','5173','1358','3825','2531') 
x = ['']*5 

for i in range(0,5): 
    a=int(m[i])/1000 
    b=int(m[i])/100-10*a 
    c=int(m[i])/10-100*a-10*b 
    d=int(m[i])%10 
    x[i]=[a,b,c,d] 

for num in range(0,10000): 
    thousand=num/1000 
    hundred=num/100-10*thousand 
    decade=num/10-100*thousand-10*hundred 
    digits=num%10 
    count=0 
    for j in range(0,5): 
     if (thousand==x[j][1] or thousand==x[j][2] or thousand==x[j][3]) and (hundred==x[j][0] or hundred==x[j][2] or hundred==x[j][3]) and (decade!=x[j][0] and decade!=x[j][1] and decade!=x[j][2] and decade!=x[j][3]) and (digits!=x[j][0] and digits!=x[j][1] and decade!=x[j][2] and decade!=x[j][3]): 
      count+=1 
     elif (thousand==x[j][1] or thousand==x[j][2] or thousand==x[j][3]) and (decade==x[j][0] or decade==x[j][1] or decade==x[j][3]) and (hundred!=x[j][0] and hundred!=x[j][1] and hundred!=x[j][2] and hundred!=x[j][3]) and (digits!=x[j][0] and digits!=x[j][1] and decade!=x[j][2] and decade!=x[j][3]): 
      count+=1 
     elif (thousand==x[j][1] or thousand==x[j][2] or thousand==x[j][3]) and (digits==x[j][0] or digits==x[j][1] or digits==x[j][2]) and (hundred!=x[j][0] and hundred!=x[j][1] and hundred!=x[j][2] and hundred!=x[j][3]) and (decade!=x[j][0] and decade!=x[j][1] and decade!=x[j][2] and decade!=x[j][3]): 
      count+=1 
     elif (hundred==x[j][0] or hundred==x[j][2] or hundred==x[j][3]) and (decade==x[j][0] or decade==x[j][1] or decade==x[j][3]) and (thousand!=x[j][0] and thousand!=x[j][1] and thousand!=x[j][2] and thousand!=x[j][3]) and (digits!=x[j][0] and digits!=x[j][1] and decade!=x[j][2] and decade!=x[j][3]): 
      count+=1 
     elif (hundred==x[j][0] or hundred==x[j][2] or hundred==x[j][3]) and (digits==x[j][0] or digits==x[j][1] or digits==x[j][2]) and (thousand!=x[j][0] and thousand!=x[j][1] and thousand!=x[j][2] and thousand!=x[j][3]) and (decade!=x[j][0] and decade!=x[j][1] and decade!=x[j][2] and decade!=x[j][3]): 
      count+=1 
     elif (decade==x[j][0] or decade==x[j][1] or decade==x[j][3]) and (digits==x[j][0] or digits==x[j][1] or digits==x[j][2]) and (thousand!=x[j][0] and thousand!=x[j][1] and thousand!=x[j][2] and thousand!=x[j][3]) and (hundred!=x[j][0] and hundred!=x[j][1] and hundred!=x[j][2] and hundred!=x[j][3]): 
      count+=1 
    if count == 5: 
     print num 

Answer 1

あなたは再帰検索を実行し、それが正しい（しかし、紛失）のあるものかもしれない数字のペアを選択するような可能性を排除するなどの代替これを、使用することができます。より多くの入力を処理することによって解決策が見つからないことが判明した場合、それはバックトラックし、次の数字の組を試します。

入力が一番深いレベルの再帰のように処理されると、4桁の数字が認識され、別の再帰的検索が開始され、これらの4桁の数字がまだ可能な位置に割り当てられます。これが成功すると、関数は直ちに発見された値を返す再帰から脱します。

def findMatch(guesses): 
    def assign(pos, digits, result): 
     if len(digits) == 0: return True 
     digit = digits[0] 
     for j in pos[digit]: 
      if result[j] == None: 
       result[j] = digit 
       if assign(pos, digits[1:], result): 
        return ''.join(map(str, result)) 
       result[j] = None 
     return False 

    def recurse(guesses, pos, must): 
     if len(must) > 4: return False 
     if len(guesses) == 0: 
      if len(must) < 4: return False # all digits in solution must be unique 
      return assign(pos, list(must), [None, None, None, None]) 
     digits = list(map(int, guesses[0])) 
     permutations = ((0,1),(2,3),(0,2),(1,3),(0,3),(1,2)) 
     for i, (j, k) in enumerate(permutations): 
      (l, m) = permutations[i^1] 
      [dig1, dig2, dig3, dig4] = [digits[j], digits[k], digits[l], digits[m]] 
      if (len(pos[dig1]) > int(j in pos[dig1]) and 
        len(pos[dig2]) > int(k in pos[dig2]) and 
        dig3 not in must and dig4 not in must): 
       saved = [pos[dig1], pos[dig2], pos[dig3], pos[dig4]] 
       # remove possibilities 
       [pos[dig1], pos[dig2], pos[dig3], pos[dig4]] = [ 
        pos[dig1] - set([j]), pos[dig2] - set([k]), set(), set()] 
       found = recurse(guesses[1:], pos, must | set((dig1,dig2))) 
       if found: 
        return found 
       # backtrack 
       [pos[dig1], pos[dig2], pos[dig3], pos[dig4]] = saved 
     return False 

    return recurse(guesses, [set([0,1,2,3]) for i in range(0,10)], set()) 

guesses = ['6087','5173','1358','3825','2531'] 
print (findMatch(guesses)) 

これは、実装したブルートフォース方式よりも速く解決策を見つけることができます。このコードでは、ソリューションが別個の数字で構成されている必要があると想定しています。