确定列表是否反对称

Question

我正在尝试编写一个函数，以便在给定关系列表时 return 对或错，无论它是否反对称。如果 (a,b) 在关系中并且 (b,a) 在关系中那么 a 必须等于 b

即给定 [["A","A"], ["A","C"], ["A","B"], ["C" ,"C"]] 会 return 真

[["A","A"], ["A","D"], ["D","A"]] 会 return false 因为 [A,D] 和 [D,A] 都在关系中但不相等

我的想法是：

def is_antisymmetric(relation):
    for a, b in relation:
        if (a,b) in relation and (b,a) in relation and a == b:
            return True
        else:
            return False

但这似乎不起作用。任何帮助将不胜感激

Answer 1

def is_antisymmetric(relation):
    for a, b in relation:
        if (a,b) in relation and (b,a) in relation and a != b:
            return False
    return True

print is_antisymmetric([("A","A"), ("A","C"), ("A","B"), ("C","C")]) # True
print is_antisymmetric([("A","A"), ("A","C"), ("C","A"), ("C","C")]) # False

或者如果您使用方括号

def is_antisymmetric(relation):
    for a, b in relation:
        if [a,b] in relation and [b,a] in relation and a != b:
            return False
    return True

print is_antisymmetric([["A","A"], ["A","C"], ["A","B"], ["C","C"]]) # True
print is_antisymmetric([["A","A"], ["A","C"], ["C","A"], ["C","C"]]) # False

Answer 2

您的方法的一个问题是 in 和 list 的成本相对昂贵 O(n)，这使得您当前的方法是 O(n^2)。一种简单有效的 O(n) 方法是将看到的每个项目添加到 set()，in 对于 set() 是 O(1) 例如：

def is_antisymmetric(relation):
    seen = set()
    for a, b in relation:
        if a == b:
            continue
        if (b, a) in seen:
            return False
        seen.add((a, b))
    return True

In []:
is_antisymmetric([["A","A"], ["A","C"], ["A","B"], ["C","C"]])
Out[]:
True

In []:
is_antisymmetric([["A","A"], ["A","D"], ["D","A"]])
Out[]:
False

一些时间...

import string
import itertools

rels = list(itertools.combinations(string.ascii_letters, 2))

当前方法（由@Xin Huang修复）：

In []:
%timeit is_antisymmetric_list(rels)
Out[]:
30.8 ms ± 727 µs per loop

使用上面的 set() 方法：

In []:
%timeit is_antisymmetric_set(rels)
Out[]:
329 µs ± 2.99 µs per loop

确定列表是否反对称

Determine whether a list is antisymmetric

python

list

relation