列表理解（Transitiv）

Question

我需要编写一个 Python 函数 isReflexive 和 isSymmetric，它们不属于 Python 的列表理解和 all 或 any 函数。示例：

isSymmetric([2,3,4],[(2,3),(3,2),(3,3),(2,4),(4,2)])
True

isTransitive([[2,3,4,5],[(2,3),(3,2),(3,3),(3,4),(2,4),(4,2),(2,2),(4,4),(4,3)]

正确

参数 1 是一个基集（列表），参数 2 是这个基集上的关系。

我试过了，但这不起作用，因为我还检查了我不必检查的元组：

def isSymmetric(g,r):
    return all([(x,y) = r for x in g for y in g])

我不知道如何解决这个问题... 还有isTransitiv不知道怎么开始D:

在此先感谢您的帮助！

Answer 1

以下基于 comp/gen 的实现将适用于对称性和传递性：

from itertools import product

def isSymmetric(g, r):
    s = set(r)
    return all(x[::-1] in s for x in s)

def isTransitive(g, r):
    s = set(r)
    return all(
       ((x,y) in s and (y,z) in s) <= ((x,z) in s) 
       for x, y, z in product(g, repeat=3)
    )

从算法 POV 来看，两者都不理想。更好的（更少和更快的检查）是：

def isSymmetric(g, r):
    s = set(r)
    while s:
        x, y = s.pop()
        if x != y:  # (x, x) does not need a partner
            try:
                s.remove((y, x))
            except KeyError:  # reverse not there!
                return False
    return True

传递性检查有点复杂。您可以使用辅助数据结构 (collections.defaultdict) 使所有检查保持不变而不是线性检查：

def isTransitive(g, r):
    d = defaultdict(set)
    for x, y in r:
        d[x].add(y)
    for x in g:  # `for x in d` reduces iterations in the general case
        for y in d[x]:  # all (x, y)
            if not all(z in d[x] for z in d[y]):  # exists (x, z) for (y, z)?
                return False
    return True

列表理解（Transitiv）

List Comprehensions (Transitiv)

python

list-comprehension

function

list

any