2010-10-01 17 views
7

tengo tres conjuntos:Python establecer pregunta intersecció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 

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?

Respuesta

2

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.

+0

muchas buenas respuestas, estoy usando 2.5.2 en este momento, así que terminé yendo con esta solución –

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

Elegante, pero preferiría 2 bucles rectas y un contador para evitar comparar cada dos elementos 2 veces, aceleraría las cosas al menos por un factor de dos –

+0

@jchl: Esto es genial y se agrega a mi conocimiento de Python – pyfunc

+0

La llamada 'bool()' es redundante. – kennytm

0

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) 
+1

¿Por qué todos los congelados? – jchl

+0

@jchl: los conjuntos no son hashables, por lo que no pueden ser elementos de un conjunto. No estoy seguro de si tiene mucho sentido hacer que el nivel superior se congele, pero parece que podría ser más rápido que un conjunto regular, y se adapta a la lógica. – intuited

+0

@jchl: Ahh, veo de lo que estás hablando ahora. Parece que tuve algún tipo de problema de indigestión mental al refacturar y luego publicar ese código. "¡Sin embargo, pasó el doctest!" De todos modos, está arreglado ahora. – intuited

0

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) 
+2

1. ¿No quieres decir 'break' en lugar de' continue'? 2. ¿Estás seguro de 'count = -1'? 3. Pierde la segunda línea y reemplaza las últimas 3 líneas por 'conteo de devolución == len (s)'. 4. ¿No sería mejor 'x! = Y y a & b'? 5. No sale temprano si un grupo no tiene amigos: ¿cuál es la base para "puede brindar un mejor rendimiento"? Mejor que qué? –

+1

Hola, hola, ... tu código está ROTO. 'count' se convierte en el número de intersecciones de conjuntos no vacíos por pares, menos 1. Esto no se parece en nada a lo que quiere el OP. Por ACCIDENTE da las respuestas correctas para los dos casos de prueba del OP. Prueba este: s2 = [set ([16, 9, 2, 10]), set ([16, 22, 14, 15]), set ([14, 2])] ... debería volver True pero su recuento es 6-1 == 5 y su código devuelve False. –

+0

@John, +1, gracias por señalar todos los errores. He editado para hacer todas las correcciones necesarias. 4. Preferí 'a & b' sobre' x! = Y' porque este último es más comúnmente cierto. ¿Es esto malo? 5. Sí, eso es correcto. Esto puede proporcionar un mejor rendimiento en comparación con los que realizan la comprobación de intersección con todos los conjuntos. – dheerosaur

2

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.

+0

Esto es significativamente más lento que su respuesta anterior. mientras que su respuesta anterior tiene un promedio de 4,7 mseg, (en la entrada aleatoria grande) esta toma 250. Los sindicatos son lo que te está matando (con esta implementación) e intuido. Teóricamente atractivo pero caro. – aaronasterling

+0

Interesante. Creo que es el gran factor constante debido a todo el código de Python (en comparación con la solución anterior que se puede evaluar casi todo en C). Además, mi primera solución funcionará bien si la llamada 'any()' puede atajar a menudo, mientras que esta solución funciona bien en todos los casos. Esta solución funciona mejor (9 frente a 24 segundos) que la primera en esta entrada: '[set ((i)) para i en el rango (N)] + [set (rango (N))]' con 'N = 10000 ', y sospecho que funcionaría aún mejor con' N' aún mayor. – jchl

+0

Me acabo de dar cuenta de que esta solución es mucho más complicada de lo necesario y aún no es óptima.Mi tercera solución es mucho mejor por ambas razones. – jchl

5

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) 
+0

puede simplemente usar 'count.setdefault (x, 0) + = 1' en lugar de la instrucción' if/else'. – aaronasterling

+1

No, no puedes. 'count.setdefault (x, 0)' no es un valor l. – jchl

+1

+1 porque evita la intersección establecida "obvia" y simplifica el problema. Desafortunadamente, no creo que obtengas suficientes votos ascendentes. Por cierto, o bien 'collections.Counter', o' count = collections.defaultdict (int) 'y' count [x] + = 1' – tzot

1

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 ;-)

+0

combinados? ¿Qué tal "combinado"? ;-) – martineau

+0

Heh, algunos diccionarios en línea listan "combinados", pero "combinados" suenan mucho mejor ;-) –

+0

Reflexionando más a fondo, los "combos" probablemente serían un nombre de variable más descriptivo, y por lo tanto aún mejor. – martineau

1

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)