Encontrar interseção de duas listas aninhadas?

468

Eu sei como obter uma interseção de duas listas simples:

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]

ou

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

print intersect(b1, b2)

Mas quando tenho que encontrar a interseção para listas aninhadas, meus problemas começam:

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]]

No final, gostaria de receber:

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

Vocês podem me dar uma mão nisso?

Relacionado

elfuego1
fonte
Qual seria a sua interseção para c1 intersect c2? Deseja simplesmente descobrir se c1 está em c2? Ou você deseja encontrar todos os elementos em c1 que aparecem em qualquer lugar em c2?
Brian R. Bondy
Leia isso e toque no intérprete.
Pithikos

Respostas:

177

Se você quiser:

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]]

Então aqui está sua solução para o Python 2:

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

No Python 3, filterretorna um iterável em vez de list, portanto, é necessário agrupar as filterchamadas com list():

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

Explicação:

A parte do filtro pega o item de cada sub-lista e verifica se está na lista de fontes c1. A compreensão da lista é executada para cada sub-lista em c2.

Brian R. Bondy
fonte
35
Você pode usar filter(set(c1).__contains__, sublist)para eficiência. Aliás, a vantagem dessa solução é que filter()preserva os tipos de cadeias e tuplas.
JFS
3
Eu gosto desse método, mas estou ficando em branco '' na minha lista resultante
Jonathan Ong
Eu adicionei Python 3 compat aqui, desde que eu estou usando isso como um alvo dupe para um joguete de uma pergunta Python 3
Antti Haapala
9
Isto lê IMO melhor com compreensões aninhadas:c3 = [[x for x in sublist if x in c1] for sublist in c2]
Eric
894

Você não precisa definir interseção. Já é uma parte de primeira classe do 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
fonte
3
Isso será mais lento que o lambda devido à conversão para definir?
Ciro Santilli # 26/14
32
@ S.Lott, algo de errado com set(b1) & set(b2)? OMI seu limpador para usar o operador.
gwg
4
Além disso, o uso setlevará a códigos com ordens de magnitude mais rápidas. Aqui está um exemplo de benchmark®: gist.github.com/andersonvom/4d7e551b4c0418de3160
andersonvom
5
Só funciona se o resultado não precisar ser solicitado.
precisa saber é o seguinte
7
Então ... essa resposta não responde de maneira alguma à pergunta, certo? Porque isso agora funciona com listas aninhadas .
precisa saber é o seguinte
60

Para pessoas que procuram encontrar a interseção de duas listas, o Asker forneceu dois 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]

e

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

print intersect(b1, b2)

Mas há um método híbrido que é mais eficiente, porque você só precisa fazer uma conversão entre lista / conjunto, em vez de três:

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

Isso será executado em O (n), enquanto o método original que envolve compreensão de lista será executado em O (n ^ 2)

Zack Burt
fonte
Como "se val em s2" é executado em O (N), a complexidade do trecho de código proposto também é O (n ^ 2)
Romeno
8
O caso médio de "val em s2" é O (1) de acordo com wiki.python.org/moin/TimeComplexity#set - portanto, em n operações, o tempo esperado é O (n) (se o pior caso é O ( n) ou O (n ^ 2) depende se esse caso médio representa um tempo amortizado ou não, mas isso não é muito importante na prática).
D Coetzee #
2
O tempo de execução é O (N), não porque ele é amortizado, mas porque a associação definida está na média de O (1) (por exemplo, ao usar a tabela de hash), é uma grande diferença, por exemplo, porque o tempo amortizado é garantido.
miroB
28

A abordagem 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))

e pode ser aplicado ao caso mais geral de 1 ou mais listas

baiacu
fonte
para permitir a entrada de lista vazia: set(*input_list[:1]).intersection(*input_list[1:]). Versão Iterator ( it = iter(input_list)): reduce(set.intersection, it, set(next(it, []))). Ambas as versões não precisam converter todas as listas de entrada para definir. Este último é mais eficiente em memória.
JFS
Use from functools import reducepara usá-lo no Python 3. Ou, melhor ainda, use um forloop explícito .
TrigonaMinima 02/08
27

Versão de compreensão pura da lista

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

Achatar variante:

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

Variante aninhada:

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

O operador & faz a interseção de dois conjuntos.

{1, 2, 3} & {2, 3, 4}
Out[1]: {2, 3}
aflaisler
fonte
Tudo bem, mas este tópico é para listas!
Rafa0809
3
O resultado da interseção de duas listas é um conjunto, portanto esta resposta é perfeitamente válida.
shrewmouse
A lista pode conter valor duplicado, mas os conjuntos não.
diewland
13

Uma maneira pitônica de fazer a interseção de 2 listas é:

[x for x in list1 if x in list2]
Flying_ostrich
fonte
2
Esta pergunta é sobre listas aninhadas. Sua resposta não responde à pergunta.
Thomas
8

Você deve nivelar usando este código (extraído de http://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks ), o código não foi testado, mas tenho certeza 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

Depois de nivelar a lista, você faz a interseção da maneira usual:


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
fonte
2
É um bom código de achatamento Geo, mas não responde à pergunta. O solicitante espera especificamente o resultado no formato [[13,32], [7,13,28], [1,6]].
Rob Young
8

Desde que intersectfoi definido, uma compreensão básica da lista é suficiente:

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

Melhoria graças à observação de S. Lott e à observação associada de TM.

>>> c3 = [list(set(c1).intersection(i)) for i in c2]
>>> c3
[[32, 13], [28, 13, 7], [1, 6]]
Emmanuel
fonte
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]]

Acho que o código a seguir funciona bem e talvez seja mais conciso se estiver usando a operação set:

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

Tem:

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

Se pedido necessário:

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

obtemos:

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

A propósito, para um estilo mais python, este também é bom:

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

Não sei se estou atrasado em responder sua pergunta. Depois de ler sua pergunta, criei uma função intersect () que pode funcionar tanto na lista quanto na lista aninhada. Eu usei recursão para definir essa função, é muito intuitiva. Espero que seja o que você está procurando:

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

Exemplo:

>>> 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
fonte
2

Você considera [1,2]interceptar [1, [2]]? Ou seja, são apenas os números importantes para você ou a estrutura da lista?

Se apenas os números, investigue como "achatar" as listas e use o set()método

descontrair
fonte
Eu gostaria de deixar a estrutura das listas inalterada.
elfuego1
1

Eu também estava procurando uma maneira de fazer isso e, eventualmente, acabou assim:

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
fonte
Se não estiver usando set.intersection, esses liners simples são o que eu também faria.
slaughter98
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]]
user3105897
fonte
0

Podemos usar métodos definidos para isso:

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
fonte
0

Para definir a interseção que leva em consideração corretamente a cardinalidade dos elementos, use 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
fonte
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]] ?

Aqui está uma maneira de definir c3que não envolve conjuntos:

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

Mas se você preferir usar apenas uma linha, poderá fazer o seguinte:

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

É uma compreensão de lista dentro de uma compreensão de lista, o que é um pouco incomum, mas acho que você não deve ter muita dificuldade em segui-la.

JL
fonte
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 mim, esta é uma maneira muito elegante e rápida de fazê-lo :)

Michal
fonte
0

lista simples pode ser feita reducefacilmente.

Tudo o que você precisa para usar o inicializador - terceiro argumento na reducefunção.

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

O código acima funciona para python2 e python3, mas você precisa importar o módulo de redução como from functools import reduce. Consulte o link abaixo para obter detalhes.

Raja Sakthiyan
fonte
-1

Maneira simples de encontrar diferença e interseção entre iterables

Use este método se a repetição for 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
fonte