Python establecer pregunta intersección

Question

tengo tres conjuntos:

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 

quiero una función que devolverá verdadero si cada conjunto en la lista se cruza con al menos otro conjunto en la lista. ¿Hay un built-in para esto o una simple lista de comprensión?

Answer 1

Es un poco detallado pero creo que es una solución bastante eficiente. Aprovecha el hecho de que cuando dos conjuntos se cruzan, podemos marcarlos como conectados. Lo hace manteniendo una lista de indicadores, siempre que la lista de conjuntos. cuando se establece i y establece j se cruzan, establece el indicador para ambos. A continuación, pasa por la lista de conjuntos y solo intenta encontrar una intersección para los conjuntos que aún no se han cruzado. Después de leer los comentarios, creo que esto es de lo que @Victor estaba hablando.

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) 

decidí que una lista vacía de conjuntos está conectado (Si usted produce un elemento de la lista, puedo producir un elemento que se cruza;). Una lista con un solo elemento se desconecta trivialmente. Es una línea para cambiar en cualquier caso si no está de acuerdo.

Answer 2

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

Answer 3

Esta estrategia no es probable que sea tan eficiente como @ sugerencia de Víctor, pero podría ser más eficiente que jchl's answer debido a una mayor utilización de las aritmética (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

Esto puede dar un mejor rendimiento dependiendo de la distribución de los conjuntos.

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

Aquí está una más eficiente (si mucho más complicado) solución, que realiza una serie lineal de intersecciones y una serie de uniones de orden O (n * log (n)), donde n es la longitud de 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 

Tenga en cuenta que esta solución solo funciona en Python> = 2.6.

Answer 6

Aquí hay una solución muy sencilla que es muy eficiente para grandes entradas:

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

Como siempre, me gustaría dar la solución inevitable 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 

Esto es muy perezoso y solo hará las intersecciones que se requieren. También puede ser un delineador muy confuso e ilegible ;-)

Answer 8

Para responder a su pregunta, no, no existe una lista de comprensión simple o incorporada que haga lo que usted desea. Aquí hay otra solución basada en itertools que es muy eficiente, sorprendentemente aproximadamente el doble de rápido que la respuesta de @ THC4k itertools usando groupby() en las pruebas de tiempo usando su entrada de muestra. Probablemente podría optimizarse un poco más, pero es muy legible como se presentó. Al igual que @AaronMcSmooth, decidí arbitrariamente qué devolver cuando no hay o hay solo un conjunto en la lista de entrada.

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)