python - 在python中测试字典的等价关系

Question

给定一个元组列表形式的关系

[(1,2), (1,3), (2,3), (2,1), (2,2), (3,2), (3,3)]

我有一个字典，将键映射到其等效类的列表

{1: [2, 3], 2: [3, 1, 2], 3: [2, 3]}

我想写一个函数，给定这个字典检查关系是否传递和对称，这意味着

∀ a, b, c : if (a,b) ∈ Relation and (b,c) ∈ Relation ==> (a,c) ∈ Relation

∀ a, b : if (a,b) ∈ Relation ==> (b,a) ∈ Relation

是否可以在不滥用嵌套循环的情况下以高效的方式编写此代码？在程序的其他部分使用字典很有帮助，但我不确定它是否在这里。

帮忙吗？

Answer 1

我认为您不需要在这里使用字典，因为在元组列表中已经很容易处理关系。如果您使用字典，您可能最终仍会使用 d.items() 将其转换为元组列表。

因为这些是关系，所以它真的应该是一组元组，而不是一个列表，它可以有重复项:

relations = {(1,2), (1,3), (2,3), (2,1), (2,2), (3,2), (3,3)}

您可以先创建一个函数来检查关系是否具有传递性:

def is_transitive(relation):
    for a, b in relation:
        for c, d in relation:
            # checks transitive property: (a, b) && (b, c) -> (a, c)
            if b == c and (a,d) not in relation:
                return False

    return True

然后您可以编写一个函数来检查关系是否与 all() 对称。 :

def is_symmetric(relation):
    # checks symmetric property: (a, b) -> (b, a)
    return all(rel[::-1] in relation for rel in relation)

然后你可以做一个简单的函数来检查上面两个函数的结合:

def check_relation(relation):
    # True and True -> True
    # True and False -> False
    # False and True -> False
    # False and False -> False
    return is_symmetric(relation) and is_transitive(relation)

其工作方式如下(未经过广泛测试):

>>> relations = {(1,2), (1,3), (2,3), (2,1), (2,2), (3,2), (3,3)}
>>> print(check_relation(relations))
False