リスト内の矛盾を見つけよう

Question

私は多くのリストを持っており、他の人と矛盾しているかどうかを知りたい。 リストは、それらによって衝突自己及び全ての関係のみ'>'と'<'されないであろう。上記の場合

list1 = ["a<4", "b<3", "c<3", "d<6"] 
list2 = ["b<6", "a<1", "c<5", "d<2"] 
list3 = ["a>7", "c<2", "b>1", "d<8"] 

、list3は"a"ためlist1に矛盾であると同時に、7より大きく、4より小さくすることができません。この場合

別の例

list4 = ["a<4", "b<3", "c>2", "d<8"] 
list5 = ["b<6", "a<6", "c<5", "d>9"] 
list6 = ["a>2", "b>1", "d<8", "c<9"] 

、list5同時に9より大きく、8よりも小さくすることができないので"d"list4に矛盾です。

Answer 1

変数を含む変数ごとにリストを単純に維持することができます。変数に上限または下限がない場合はNoneを使用できます。

制約を評価するたびにリストを更新し、下限が上限よりも大きくなると競合が発生することがわかります。

今、私たちは、わずか数の部品が必要です。制約を導出ステップを解析

• を。
• バリアントマネージャは、境界を維持しチェックします。

次のように変数マネージャが動作することができます：

def update_variables(var_dict,variable,constraint,value): 
    la = var_dict.get(variable) 
    if la is None: 
     la = [None,None] 
     var_dict[variable] = la 
    if constraint == '>' and (la[0] is None or value > la[0]): 
     la[0] = value 
    elif constraint == '<' and (la[1] is None or value < la[1]): 
     la[1] = value 
    return la[0] is None or la[1] is None or la[0] < la[1] 

まず変数がすでに辞書の一部である場合、我々は確認してください。そうでない場合は[None,None]を追加します。次に、制約に対応するインデックス（の場合は0、'<'の場合は1）を更新して、境界を更新します。最後に、バインディングがまだ可能かどうかを確認します。その場合、我々はTrueを返す。それ以外の場合はFalseを返します。そのような拘束されたエラーから、我々は2つのリストが矛盾していることを知っている。

これで、リストを処理し、それに応じてマネージャを更新する必要があります。そこでここでは、すべての文字列がフォーマット\w+（変数の名前を）持っていることを前提としてい

(\w+)\s*(<|>)\s*(-?\d+) 

、'<'または'>'、最後に値-?\d+続く：そこで我々は、正規表現を開発しました。リストからそのような文字列を取得するたびに、その文字列を解析し、マネージャを更新し、構成がまだ有効かどうかを確認します。だから、これは次のようになります。

import re 

def conflict(lista,listb): 
    manager = {} 
    rgx = re.compile(r'(\w+)\s*(<|>)\s*(-?\d+)') 
    for listi in (lista,listb): 
     for constraint in listi: 
      mat = rgx.match(constraint) 
      if mat: 
       var,con,val = mat.groups() 
       val = int(val) 
       if not update_variables(manager,var,con,val): 
        return True # the lists are conflicting 
      else: 
       raise Exception('Could not parse constraint "%s"'%constraint) 
    return False # the lists do not conflict 

これが生成します。

>>> conflict(list3,list1) 
True 
>>> conflict(list1,list1) 
False 
>>> conflict(list1,list2) 
False 
>>> conflict(list1,list3) 
True 
>>> conflict(list2,list3) 
True 

Answer 2

あなたがSymPyを試みることができます。あなたのリストの

from sympy.solvers import solve 
from sympy import symbols 
from sympy.parsing.sympy_parser import parse_expr 

a, b, c, d = symbols('a b c d') 
list1 = ["a<4", "b<3", "c<3", "d<6"] 
list2 = ["b<6", "a<1", "c<5", "d<2"] 
list3 = ["a>7", "c<2", "b>1", "d<8"] 

l1 = [parse_expr(eq) for eq in list1] 
l2 = [parse_expr(eq) for eq in list2] 
l3 = [parse_expr(eq) for eq in list3] 

print(solve(l1 + l2)) 
print(solve(l1 + l3)) 
print(solve(l2 + l3)) 

文字列はparse_exprと不平等に解析されます。次に、リストを連結して+とし、一度に8つの不等式を解いてみる必要があります。あなたがFalseを得た場合、それは不可能であり、従ってあなたは矛盾しています。そうでなければ、不等式を満たすために正しい値a, b, c, dの式を得る。あなたは、文字列の多くのリストを持っている場合、あなたは、私は手動で、ここで行ったように3つの組み合わせl1 + l2が唯一の存在としてのすべてのリストを結合する方法を見つけなければならない。もちろん、

def contradiction(l_i, l_j): 
    s = solve(l_i + l_j) 
    if s==False: return True 
    else: return False 

：だから、このような何かを書くことができl1 + l3およびl2 + l3。また、大きなリストの場合、パフォーマンスが悪くなる可能性があることに注意してください。