如何测试一个列表中的所有项目都是不相交的？

Question

给定一个包含多个iterable的列表，我想测试是否所有项都是disjoint。在

two sets are said to be disjoint if they have no element in common

示例：

iterables = ["AB", "CDE", "AF"]
all_disjoint(iterables)
# False

iterables = ["AB", "CDE", "FG"]
all_disjoint(iterables)
# True

Python集合有一个工作的isdisjoint方法，但它是为一次测试两个元素而设计的。一种方法是将此方法应用于每对元素组：

^{pr2}$

这里我修改了pairwiseitertools recipe，最后一次附加第一个元素。但这并不完全正确，因为它只测试相邻的项，而不是针对列表中所有其他项的每个项。我想用更少的代码更优雅地测试所有元素。有更简单的方法吗？在

Answer 1

IIUC，你可以把你的字符串列表合并起来，然后检查合并后的长度是否等于这个字符串的集合的长度。在

您可以使用''.join连接字符串并定义函数：

def all_disjoint(iterables):
    total = ''.join(iterables)
    return len(total) == len(set(total))

现在，测试：

^{pr2}$

Answer 2

考虑到你所说的要测试每个项目是否与所有其他项目不相交，我认为这符合您的要求：

import itertools as it

def all_disjoint(x):
    return all((set(p0).isdisjoint(set(p1))) for p0, p1 in it.combinations(x, 2))

iterables = ['AB', 'CDE', 'AF']
print(all_disjoint(iterables))  # -> False

iterables = ['AB', 'CDE', 'FG']
print(all_disjoint(iterables))  # -> True

# your code gives different answer on this one 
# (because it doesn't check what you want)
iterables = ['AB', 'CDE', 'AH', 'FG']
print(all_disjoint(iterables))  # -> False

Answer 3

首先，set(list('AB'))将产生集合{'A', 'B'}。在

第二，通过对s进行枚举，然后使用for s2 in s[n+1:]，只需查看上对角线，从而避免了将值与自身或另一对进行比较的需要。例如，如果s = ['A', 'B', 'C']，那么[（s1，s2）For n，s1 in enumerate（s）For s s[n+1:]]中的s2将得到：[('A', 'B'), ('A', 'C'), ('B', 'C')]。如果要从itertools导入combinations，这相当于list(combinations(s, 2))的结果。在

鉴于上述情况，我使用any生成器来比较每个子集之间是否缺少交集。在

由于any构造，它将在第一次观察到公共元素时短路，从而避免了计算每对元素的需要。在

s = ['AB', 'CDE', 'AF']
>>> not any(set(list(s1)).intersection(set(list(s2))) 
            for n, s1 in enumerate(s) for s2 in s[n+1:])
False

s = ['AB', 'CDE', 'FG']
>>> not any(set(list(s1)).intersection(set(list(s2))) 
            for n, s1 in enumerate(s) for s2 in s[n+1:])
True