+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

暂无数据

在清单中找到矛盾

发布于2020-11-28 09:06     阅读(1009)     评论(0)     点赞(14)     收藏(1)


0

1

2

3

4

5

6

7

8

9

我有很多清单,我想查找是否与他人矛盾。列表不会由他们自己冲突,并且所有关系都是'>'并且'<'

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"]

在上述情况下,由于不能同时大于7和小于4而list3矛盾list1"a"

另一个例子

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"]

在这种情况下,由于不能同时大于9和小于8而list5矛盾list4"d"


解决方案


您可以简单地维护每个包含上限和下限的变量列表如果变量没有上限或下限,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从此类绑定错误的那一刻起,我们知道这两个列表是冲突的。

现在,我们仍然需要处理列表并相应地更新管理器。因此我们开发了一个正则表达式:

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

因此,这里我们假设每个字符串都具有格式\w+(变量的名称),后跟一个'<'or或'>'最后一个value -?\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

0

1

2

3

4

5



所属网站分类: 技术文章 > 问答

作者:黑洞官方问答小能手

链接: https://www.pythonheidong.com/blog/article/634476/a62af4e0960b89c95e52/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

14 0
收藏该文
已收藏

评论内容:(最多支持255个字符)