Python задать вопрос пересечения

Question

У меня есть три набора:

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 

хочу функцию, которая возвращает истину, если каждый набор в списке пересекается с, по меньшей мере, одного другого набора в списке. Есть ли встроенное средство для этого или простого понимания списка?

Answer 1

Это немного подробный, но я думаю, что это довольно эффективное решение. Он использует тот факт, что при пересечении двух множеств мы можем отметить их как связанные. Он делает это, сохраняя список флагов, пока список наборов. когда установлено i и установлено j пересекаются, он устанавливает флаг для обоих из них. Затем он перебирает список наборов и только пытается найти пересечение для множеств, которые еще не были пересечены. После прочтения комментариев, я думаю, это то, о чем говорил @Victor.

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) 

Я решил, что пустой список наборов подключен (Если вы производите элемент списка, я могу производить элемент, который он пересекает;). Список только с одним элементом несвязно тривиально. Это одна строка, которая изменится в любом случае, если вы не согласны.

Answer 2

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

Answer 3

Эта стратегия, вероятно, не будет столь же эффективным, как @ предложение Виктора, но может быть более эффективным, чем jchl's answer в связи с увеличением использования множества арифметических (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

Это может обеспечить лучшую производительность в зависимости от распределения комплектов.

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

Вот более эффективным (если гораздо более сложным) решение, которое выполняет линейное число пересечений и ряд объединений порядка О (п * журнала (п)), где п длина 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 

Обратите внимание, что это решение работает только на Python> = 2.6.

Answer 6

Вот очень простое решение, которое очень эффективно для больших входов:

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

Как обычно, я хотел бы дать неизбежное 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 

Это действительно ленивы и будут выполнять только пересечения, которые требуются. Это также может быть очень запутанным и нечитаемым oneliner ;-)

Answer 8

Чтобы ответить на ваш вопрос, нет, нет встроенного или простого понимания списка, которое делает то, что вы хотите. Вот еще одно решение на основе itertools, которое очень эффективно - на удивление примерно в два раза быстрее, чем @TAC4k's itertools, используя groupby() в тестах времени, используя ваш образец ввода. Вероятно, он может быть оптимизирован немного дальше, но очень читаем, как представлено. Подобно @AaronMcSmooth, я произвольно решил, что возвращать, когда в списке ввода нет или только один набор.

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)