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

Question

给定多个迭代列表，我想测试所有项目是否为disjoint。

两组被认为是不相交如果它们的共同点

实施例没有元素：

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

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

Python的集合具有一个isdisjoint方法，该方法有效，但它被设计用于一次测试两个元素。一种方法是将该方法应用于元件的每个成对组：

import itertools as it 


def pairwise_(iterable): 
    """s -> (s0,s1), (s1,s2), (s2,s3), ..., (sn,s0)""" 
    # Modified: the last element wraps back to the first element. 
    a, b = it.tee(iterable, 2) 
    first = next(b, None) 
    b = it.chain(b, [first]) 
    return zip(a, b) 


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

在这里，我修改pairwiseitertools recipe附着在第一元件最后一次。这是不正确的，因为它只测试邻近的项目，而不是每个项目对列表中的所有其他项目。我想用更少的代码更优雅地测试所有元素。有没有更简单的方法来做到这一点？

Answer 1

IIUC，你可以把你的字符串列表，合并它们，然后检查组合的长度是否等于该字符串的等效长度。

您可以使用''.join加入你的字符串，并定义功能：

In [17]: def all_disjoint(iterables): 
    ...:  total = ''.join(iterables) 
    ...:  return len(total) == len(set(total)) 
    ...: 

现在，测试：

所有的

In [18]: all_disjoint(['AB', 'CDE', 'AF']) 
Out[18]: False 

In [19]: all_disjoint(['AB', 'CDE', 'FG']) 
Out[19]: True 

Answer 2

首先，set(list('AB'))将导致集合{'A', 'B'}。

其次，通过枚举s然后使用for s2 in s[n+1:]只查看上对角线并避免需要比较其自身或其他对的值。例如，如果s = ['A', 'B', 'C']，则[（s1，s2）代表n，s1代表s [n + 1：]中s2的s1）将导致：[('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 

Answer 3

我为其他感兴趣的人添加这些答案。

方法1：我意识到这可以用multiset（Counter）完成。

import itertools as it 
import collections as ct 


def all_disjoint(iterables): 
    return all(not v-1 for v in ct.Counter(it.chain.from_iterable(iterables)).values()) 

---

方法2：从more_itertools库，more_itertools.unique_to_each产生从每一个迭代的所有独特的项目。下面的代码结果的长度比较原始iterables：

import more_itertools as mit 

def all_disjoint(iterables): 
    return all(len(x) == len(y) for x, y in zip(iterables, mit.unique_to_each(*iterables))) 

Answer 4

鉴于你说称要测试每个项目是不相交所有其他项目，我想这你想要做什么：

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