如何測試列表中的所有項目是不相交的？

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