List Comprehensions (Transitiv)

Question

I need to write a Python function isReflexive and isSymmetric, which are exclusive from Python's List Comprehensions and the all or any function. Example:

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

True

The 1 argument is a base set (list) and the 2 argument is a relation over this base set.

I tried this, but this doesnt work, because I also check tuples that I don't have to check:

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

I don't know how to sovle the problem... And isTransitiv I don't know how to start D:

Thanks in advance for all the help!

Answer 1

The following comp/gen based implementations will work for symmetry and transitivity:

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)
    )

Both are not ideal from an algorithmic POV. Better (less and faster checks) would be:

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

The transitivity check is a bit more complicated. You can use an auxiliary data structure (collections.defaultdict) to make all the checks constant instead of linear:

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