¿Encontrar intersección de dos listas anidadas?

468

Sé cómo obtener una intersección de dos listas planas:

b1 = [1,2,3,4,5,9,11,15]
b2 = [4,5,6,7,8]
b3 = [val for val in b1 if val in b2]

o

def intersect(a, b):
    return list(set(a) & set(b))

print intersect(b1, b2)

Pero cuando tengo que encontrar la intersección de las listas anidadas, comienzan mis problemas:

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

Al final me gustaría recibir:

c3 = [[13,32],[7,13,28],[1,6]]

¿Pueden echarme una mano con esto?

Relacionado

elfuego1
fuente
¿Cuál sería su intersección para c1 intersect c2? ¿Quieres simplemente encontrar si c1 está en c2? ¿O desea encontrar todos los elementos en c1 que aparecen en cualquier lugar de c2?
Brian R. Bondy
Lea esto y juegue en el intérprete.
Pithikos

Respuestas:

177

Si tu quieres:

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
c3 = [[13, 32], [7, 13, 28], [1,6]]

Entonces aquí está su solución para Python 2:

c3 = [filter(lambda x: x in c1, sublist) for sublist in c2]

En Python 3 filterdevuelve un iterable en lugar de list, por lo que debe ajustar las filterllamadas con list():

c3 = [list(filter(lambda x: x in c1, sublist)) for sublist in c2]

Explicación:

La parte del filtro toma cada elemento de la sublista y verifica si está en la lista de origen c1. La comprensión de la lista se ejecuta para cada sublista en c2.

Brian R. Bondy
fuente
35
Puedes usar filter(set(c1).__contains__, sublist)para la eficiencia. Por cierto, la ventaja de esta solución es que filter()conserva los tipos de cadenas y tuplas.
jfs el
3
Me gusta este método, pero me estoy quedando en blanco '' en mi lista resultante
Jonathan Ong
Agregué Python 3 compat aquí, ya que estoy usando esto como un objetivo de engaño para una pregunta de Python 3
Antti Haapala
99
Esto lee mejor OMI con comprensiones anidadas:c3 = [[x for x in sublist if x in c1] for sublist in c2]
Eric
894

No necesita definir la intersección. Ya es una parte de primera clase del set.

>>> b1 = [1,2,3,4,5,9,11,15]
>>> b2 = [4,5,6,7,8]
>>> set(b1).intersection(b2)
set([4, 5])
S.Lott
fuente
3
¿Será esto más lento que lambda debido a la conversión al conjunto?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
32
@ S.Lott, ¿tiene algo de malo set(b1) & set(b2)? OMI es más limpio para usar el operador.
gwg
44
Además, el uso setconducirá a un código que es de órdenes de magnitud más rápido. Aquí hay una muestra de benchmark®: gist.github.com/andersonvom/4d7e551b4c0418de3160
andersonvom
55
Solo funciona si el resultado no tiene que ser ordenado.
Borbag
77
Entonces ... esta respuesta de ninguna manera responde a la pregunta, ¿verdad? Porque esto ahora funciona con listas anidadas .
Mayou36
60

Para las personas que solo buscan encontrar la intersección de dos listas, el Asker proporcionó dos métodos:

b1 = [1,2,3,4,5,9,11,15]
b2 = [4,5,6,7,8]
b3 = [val for val in b1 if val in b2]

y

def intersect(a, b):
     return list(set(a) & set(b))

print intersect(b1, b2)

Pero hay un método híbrido que es más eficiente, porque solo tiene que hacer una conversión entre lista / conjunto, en lugar de tres:

b1 = [1,2,3,4,5]
b2 = [3,4,5,6]
s2 = set(b2)
b3 = [val for val in b1 if val in s2]

Esto se ejecutará en O (n), mientras que su método original de comprensión de listas se ejecutará en O (n ^ 2)

Zack Burt
fuente
Como "if val in s2" se ejecuta en O (N), la complejidad del fragmento de código propuesto también es O (n ^ 2)
Romeno
8
El caso promedio de "val en s2" es O (1) de acuerdo con wiki.python.org/moin/TimeComplexity#set - por lo tanto, en n operaciones, el tiempo esperado es O (n) (si el peor de los casos es O ( n) u O (n ^ 2) depende de si este caso promedio representa un tiempo amortizado o no, pero esto no es muy importante en la práctica).
D Coetzee
2
El tiempo de ejecución es O (N) no porque se amortice, sino porque la membresía establecida es en promedio O (1) (por ejemplo, cuando se usa la tabla hash), es una gran diferencia, por ejemplo, porque el tiempo amortizado está garantizado.
miroB
28

El enfoque funcional:

input_list = [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7]]

result = reduce(set.intersection, map(set, input_list))

y se puede aplicar al caso más general de las listas 1+

pez globo
fuente
para permitir que la lista de entrada vacío: set(*input_list[:1]).intersection(*input_list[1:]). Versión iterador ( it = iter(input_list)): reduce(set.intersection, it, set(next(it, []))). Ambas versiones no requieren convertir todas las listas de entrada para establecer. Este último es más eficiente en memoria.
jfs
Use from functools import reducepara usarlo en Python 3. O mejor aún, use un forbucle explícito .
TrigonaMinima
27

Versión de comprensión de lista pura

>>> c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
>>> c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
>>> c1set = frozenset(c1)

Aplanar variante:

>>> [n for lst in c2 for n in lst if n in c1set]
[13, 32, 7, 13, 28, 1, 6]

Variante anidada:

>>> [[n for n in lst if n in c1set] for lst in c2]
[[13, 32], [7, 13, 28], [1, 6]]
jfs
fuente
20

El operador & toma la intersección de dos conjuntos.

{1, 2, 3} & {2, 3, 4}
Out[1]: {2, 3}
aflaisler
fuente
Bien, ¡pero este tema es para listas!
Rafa0809
3
El resultado de la intersección de dos listas es un conjunto, por lo que esta respuesta es perfectamente válida.
musaraña
La lista puede contener valores duplicados pero los conjuntos no.
Diewland
13

Una forma pitónica de tomar la intersección de 2 listas es:

[x for x in list1 if x in list2]
Flying_ostrich
fuente
2
Esta pregunta es sobre listas anidadas. Su respuesta no responde la pregunta.
Thomas
8

Debería aplanar usando este código (tomado de http://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks ), el código no ha sido probado, pero estoy bastante seguro de que funciona:


def flatten(x):
    """flatten(sequence) -> list

    Returns a single, flat list which contains all elements retrieved
    from the sequence and all recursively contained sub-sequences
    (iterables).

    Examples:
    >>> [1, 2, [3,4], (5,6)]
    [1, 2, [3, 4], (5, 6)]
    >>> flatten([[[1,2,3], (42,None)], [4,5], [6], 7, MyVector(8,9,10)])
    [1, 2, 3, 42, None, 4, 5, 6, 7, 8, 9, 10]"""

    result = []
    for el in x:
        #if isinstance(el, (list, tuple)):
        if hasattr(el, "__iter__") and not isinstance(el, basestring):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

Después de aplanar la lista, realiza la intersección de la manera habitual:


c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

def intersect(a, b):
     return list(set(a) & set(b))

print intersect(flatten(c1), flatten(c2))
Geo
fuente
2
Es un buen código de aplanamiento Geo, pero no responde la pregunta. El autor de la pregunta espera específicamente el resultado en la forma [[13,32], [7,13,28], [1,6]].
Rob Young
8

Desde que intersectse definió, una comprensión básica de la lista es suficiente:

>>> c3 = [intersect(c1, i) for i in c2]
>>> c3
[[32, 13], [28, 13, 7], [1, 6]]

Mejora gracias a la observación de S. Lott y la observación asociada de TM .:

>>> c3 = [list(set(c1).intersection(i)) for i in c2]
>>> c3
[[32, 13], [28, 13, 7], [1, 6]]
Emmanuel
fuente
5

Dado:

> c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]

> c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

Creo que el siguiente código funciona bien y tal vez sea más conciso si se usa la operación set:

> c3 = [list(set(f)&set(c1)) for f in c2] 

Llegó:

> [[32, 13], [28, 13, 7], [1, 6]]

Si se necesita orden:

> c3 = [sorted(list(set(f)&set(c1))) for f in c2] 

tenemos:

> [[13, 32], [7, 13, 28], [1, 6]]

Por cierto, para un estilo más python, este también está bien:

> c3 = [ [i for i in set(f) if i in c1] for f in c2]
Steven
fuente
3

No sé si llego tarde a responder tu pregunta. Después de leer su pregunta, se me ocurrió una función intersect () que puede funcionar tanto en la lista como en la lista anidada. Utilicé la recursión para definir esta función, es muy intuitiva. Espero que sea lo que estás buscando:

def intersect(a, b):
    result=[]
    for i in b:
        if isinstance(i,list):
            result.append(intersect(a,i))
        else:
            if i in a:
                 result.append(i)
    return result

Ejemplo:

>>> c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
>>> c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
>>> print intersect(c1,c2)
[[13, 32], [7, 13, 28], [1, 6]]

>>> b1 = [1,2,3,4,5,9,11,15]
>>> b2 = [4,5,6,7,8]
>>> print intersect(b1,b2)
[4, 5]
Mrsky Boatin
fuente
2

¿Consideras [1,2]cruzarte con [1, [2]]? Es decir, ¿solo le importan los números o la estructura de la lista?

Si solo son los números, investigue cómo "aplanar" las listas, luego use el set()método.

relajarse
fuente
Me gustaría dejar la estructura de las listas sin cambios.
elfuego1
1

También estaba buscando una manera de hacerlo, y finalmente terminó así:

def compareLists(a,b):
    removed = [x for x in a if x not in b]
    added = [x for x in b if x not in a]
    overlap = [x for x in a if x in b]
    return [removed,added,overlap]
Remco van Zuijlen
fuente
Si no usa set.intersection, estos simples revestimientos son lo que yo también haría.
masacre98
0
c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]

c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

c3 = [list(set(c2[i]).intersection(set(c1))) for i in xrange(len(c2))]

c3
->[[32, 13], [28, 13, 7], [1, 6]]
usuario3105897
fuente
0

Podemos usar métodos establecidos para esto:

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

   result = [] 
   for li in c2:
       res = set(li) & set(c1)
       result.append(list(res))

   print result
Birendra Kumar
fuente
0

Para definir la intersección que tenga en cuenta correctamente la cardinalidad de los elementos, utilice Counter:

from collections import Counter

>>> c1 = [1, 2, 2, 3, 4, 4, 4]
>>> c2 = [1, 2, 4, 4, 4, 4, 5]
>>> list((Counter(c1) & Counter(c2)).elements())
[1, 2, 4, 4, 4]
James Hirschorn
fuente
0
# Problem:  Given c1 and c2:
c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
# how do you get c3 to be [[13, 32], [7, 13, 28], [1, 6]] ?

Aquí hay una forma de establecer c3que no involucra conjuntos:

c3 = []
for sublist in c2:
    c3.append([val for val in c1 if val in sublist])

Pero si prefiere usar solo una línea, puede hacer esto:

c3 = [[val for val in c1 if val in sublist]  for sublist in c2]

Es una comprensión de lista dentro de una comprensión de lista, lo cual es un poco inusual, pero creo que no deberías tener demasiados problemas para seguirla.

JL
fuente
0
c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
c3 = [list(set(i) & set(c1)) for i in c2]
c3
[[32, 13], [28, 13, 7], [1, 6]]

Para mí, esta es una forma muy elegante y rápida de hacerlo :)

Michal
fuente
0

La lista plana se puede hacer reducefácilmente.

Todo lo que necesitas para usar initializer - tercer argumento en la reducefunción.

reduce(
   lambda result, _list: result.append(
       list(set(_list)&set(c1)) 
     ) or result, 
   c2, 
   [])

El código anterior funciona tanto para python2 como para python3, pero debe importar el módulo de reducción como from functools import reduce. Consulte el siguiente enlace para más detalles.

Raja Sakthiyan
fuente
-1

Manera simple de encontrar la diferencia y la intersección entre iterables

Use este método si la repetición es importante

from collections import Counter

def intersection(a, b):
    """
    Find the intersection of two iterables

    >>> intersection((1,2,3), (2,3,4))
    (2, 3)

    >>> intersection((1,2,3,3), (2,3,3,4))
    (2, 3, 3)

    >>> intersection((1,2,3,3), (2,3,4,4))
    (2, 3)

    >>> intersection((1,2,3,3), (2,3,4,4))
    (2, 3)
    """
    return tuple(n for n, count in (Counter(a) & Counter(b)).items() for _ in range(count))

def difference(a, b):
    """
    Find the symmetric difference of two iterables

    >>> difference((1,2,3), (2,3,4))
    (1, 4)

    >>> difference((1,2,3,3), (2,3,4))
    (1, 3, 4)

    >>> difference((1,2,3,3), (2,3,4,4))
    (1, 3, 4, 4)
    """
    diff = lambda x, y: tuple(n for n, count in (Counter(x) - Counter(y)).items() for _ in range(count))
    return diff(a, b) + diff(b, a)
Connor
fuente