Python thiết ngã tư vấn

Question

Tôi có ba bộ:

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])] # true, 16 and 14 
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] # false 

Tôi muốn có một chức năng đó sẽ trở lại True nếu mỗi bộ trong danh sách giao cắt với ít nhất một bộ khác trong danh sách. Có một built-in cho điều này hoặc một danh sách đơn giản hiểu?

Answer 1

Đó là một chút chi tiết nhưng tôi nghĩ đó là một giải pháp khá hiệu quả. Nó tận dụng lợi thế của thực tế là khi hai bộ giao nhau, chúng ta có thể đánh dấu cả hai đều được kết nối. Nó làm điều này bằng cách giữ một danh sách các lá cờ miễn là danh sách các bộ. khi đặt i và đặt j giao nhau, nó đặt cờ cho cả hai. Sau đó nó lặp qua danh sách các bộ và chỉ cố gắng tìm một giao lộ cho các tập chưa được giao nhau. Sau khi đọc các bình luận, tôi nghĩ đây là những gì @Victor đang nói đến.

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])] # true, 16 and 14 
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] # false 


def connected(sets): 
    L = len(sets) 

    if not L: return True 
    if L == 1: return False 

    passed = [False] * L 
    i = 0 
    while True: 
     while passed[i]: 
      i += 1 
      if i == L: 
       return True 

     for j, s in enumerate(sets): 
      if j == i: continue 
      if sets[i] & s: 
       passed[i] = passed[j] = True 
       break 
     else: 
      return False 


print connected(s0) 
print connected(s1) 

Tôi đã quyết định rằng danh sách bộ trống rỗng được kết nối (Nếu bạn tạo thành phần của danh sách, tôi có thể tạo thành phần mà nó cắt;). Danh sách chỉ có một phần tử bị ngắt kết nối một cách tầm thường. Đó là một dòng để thay đổi trong cả hai trường hợp nếu bạn không đồng ý.

Answer 2

all(any(a & b for a in s if a is not b) for b in s) 

Answer 3

Chiến lược này là không có khả năng được hiệu quả như @ đề nghị Victor, nhưng có thể hiệu quả hơn jchl's answer do tăng sử dụng bộ số học (union).

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])] 
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] 

def freeze(list_of_sets): 
    """Transform a list of sets into a frozenset of frozensets.""" 
    return frozenset(frozenset(set_) for set_ in list_of_sets) 

def all_sets_have_relatives(set_of_sets): 
    """Check if all sets have another set that they intersect with. 

    >>> all_sets_have_relatives(s0) # true, 16 and 14 
    True 
    >>> all_sets_have_relatives(s1) # false 
    False 
    """ 
    set_of_sets = freeze(set_of_sets) 
    def has_relative(set_): 
     return set_ & frozenset.union(*(set_of_sets - set((set_,)))) 
    return all(has_relative(set) for set in set_of_sets) 

Answer 4

Điều này có thể mang lại hiệu suất tốt hơn tùy thuộc vào việc phân phối các bộ.

def all_intersect(s): 
    count = 0 
    for x, a in enumerate(s): 
     for y, b in enumerate(s): 
     if a & b and x!=y: 
      count += 1 
      break 
    return count == len(s) 

Answer 5

Dưới đây là một hiệu quả hơn (nếu phức tạp hơn nhiều) giải pháp, mà thực hiện một số tuyến tính của nút giao thông và một số đoàn thể của trật tự O (n * log (n)), trong đó n là chiều dài của s :

def f(s): 
    import math 
    j = int(math.log(len(s) - 1, 2)) + 1 
    unions = [set()] * (j + 1) 
    for i, a in enumerate(s): 
     unions[:j] = [set.union(set(), *s[i+2**k:i+2**(k+1)]) for k in range(j)] 
     if not (a & set.union(*unions)): 
      return False 
     j = int(math.log(i^(i + 1), 2)) 
     unions[j] = set.union(a, *unions[:j]) 
    return True 

Lưu ý rằng giải pháp này chỉ hoạt động trên Python> = 2.6.

Answer 6

Dưới đây là một giải pháp rất đơn giản mà rất hiệu quả cho đầu vào lớn:

def g(s): 
    import collections 
    count = collections.defaultdict(int) 
    for a in s: 
     for x in a: 
      count[x] += 1 
    return all(any(count[x] > 1 for x in a) for a in s) 

Answer 7

Như thường lệ tôi muốn cung cấp cho các giải pháp không thể tránh khỏi itertools ;-)

from itertools import combinations, groupby 
from operator import itemgetter 


def any_intersects(sets): 
    # we are doing stuff with combinations of sets 
    combined = combinations(sets,2) 
    # group these combinations by their first set 
    grouped = (g for k,g in groupby(combined, key=itemgetter(0))) 
    # are any intersections in each group 
    intersected = (any((a&b) for a,b in group) for group in grouped) 
    return all(intersected) 


s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])] 
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] 
print any_intersects(s0) # True 
print any_intersects(s1) # False 

Điều này thực sự lười biếng và sẽ chỉ thực hiện các giao lộ được yêu cầu. Nó cũng có thể là một oneliner rất khó hiểu và không thể đọc ;-)

Answer 8

Để trả lời câu hỏi của bạn, không, không có một danh sách được xây dựng trong hoặc đơn giản hiểu rằng những gì bạn muốn. Đây là một giải pháp khác dựa trên itertools rất hiệu quả - đáng kinh ngạc gấp hai lần câu trả lời itertools của @ THC4k sử dụng groupby() trong các thử nghiệm định thời bằng cách sử dụng đầu vào mẫu của bạn. Nó có thể được tối ưu hóa thêm một chút, nhưng rất dễ đọc như đã trình bày. Giống như @AaronMcSmooth, tôi tự ý quyết định những gì cần trả lại khi không có hoặc chỉ có một bộ trong danh sách đầu vào.

from itertools import combinations 

def all_intersect(sets): 
    N = len(sets) 
    if not N: return True 
    if N == 1: return False 

    intersected = [False] * N 
    for i,j in combinations(xrange(N), 2): 
     if not intersected[i] or not intersected[j]: 
      if sets[i] & sets[j]: 
       intersected[i] = intersected[j] = True 
    return all(intersected)