Python 与元组集的关系

Question

我试图确定元组集是否具有某种类型的关系。我正在尝试找出传递关系和复合关系。

对于传递关系:

 # A relation 'Relation' is called transitive when:
 # ∀ (a, b) ∈ Relation, (b, c) ∈ Relation ==> (a, c) ∈ Relation

例如:

>>> {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)} # Should be False
>>> {(1,1), (2,1), (3,1), (3,2), (4,1), (4,2), (4,3)} # Should be True

对于复合关系:

# The composite of relations 'R1' and 'R2' is the relation consisting
# of tuples (a,c), such that (a,b) ∈ R1 and (b,c) ∈ R2

例如:

{(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)} == R1={(1,1), (1,4), (2,3), (3,1), (3,4)}, R2={(1,0), (2,0), (3,1), (3,2), (4,1)}
# Should return True

我不确定如何开始编写这些函数。任何帮助我开始的帮助将不胜感激。谢谢!

编辑:以下是我能够成功编码的一些其他关系:

# Reflexive Relation
# A relation 'Relation' on a set 'Set' is called reflexive when:
# ∀ a ∈ Set, (a,a) ∈ Relation
def is_reflexive(Set, Relation):
    newSet = {(a, b) for a in Set for b in Set if a == b}
    if Relation >= newSet:
        return True

    return False

# Symmetric Relation
# A relation 'Relation' is called symmetric when:
#  ∀ (a, b) ∈ Relation, (b, a) ∈ Relation
def is_symmetric(Relation):
    if all(tup[::-1] in Relation for tup in Relation):
        return True


    return False

Answer 1

对于传递测试，只需转换 Python 中的数学定义:

def is_transitive(relation):
    for a,b in relation:
        for c,d in relation:
            if b == c and ((a,d) not in relation):
                    # print (a,b),(c,d) # uncomment for tests...
                    return False
    return True