Schnittpunkt zweier verschachtelter Listen finden?

468

Ich weiß, wie man einen Schnittpunkt zweier flacher Listen erhält:

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]

oder

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

print intersect(b1, b2)

Aber wenn ich Schnittpunkte für verschachtelte Listen finden muss, beginnen meine Probleme:

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

Am Ende möchte ich erhalten:

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

Könnt ihr mir dabei helfen?

verbunden

elfuego1
quelle
Was wäre Ihre Kreuzung für c1 Kreuzung c2? Möchten Sie einfach herausfinden, ob c1 in c2 ist? Oder möchten Sie alle Elemente in c1 finden, die irgendwo in c2 erscheinen?
Brian R. Bondy
Lesen Sie dies und spielen Sie im Dolmetscher.
Pithikos

Antworten:

177

Falls Sie es wollen:

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

Dann ist hier Ihre Lösung für Python 2:

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

In Python 3 wird filteranstelle von iterable eine iterable zurückgegeben list, sodass Sie filterAufrufe mit list()folgenden Zeilen umschließen müssen :

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

Erläuterung:

Der Filterteil nimmt das Element jeder Unterliste und prüft, ob es in der Quellliste c1 enthalten ist. Das Listenverständnis wird für jede Unterliste in c2 ausgeführt.

Brian R. Bondy
quelle
35
Sie können filter(set(c1).__contains__, sublist)für die Effizienz verwenden. Übrigens besteht der Vorteil dieser Lösung darin, dass filter()Zeichenfolgen und Tupeltypen erhalten bleiben.
JFS
3
Ich mag diese Methode, aber ich werde leer in meiner resultierenden Liste
Jonathan Ong
Ich habe hier Python 3-Kompatibilität hinzugefügt, da ich dies als Dupe-Ziel für eine Dupe einer Python 3-Frage verwende
Antti Haapala
9
Dies liest sich besser IMO mit verschachtelten Verständnissen:c3 = [[x for x in sublist if x in c1] for sublist in c2]
Eric
894

Sie müssen keine Kreuzung definieren. Es ist bereits ein erstklassiger Teil des Sets.

>>> b1 = [1,2,3,4,5,9,11,15]
>>> b2 = [4,5,6,7,8]
>>> set(b1).intersection(b2)
set([4, 5])
S.Lott
quelle
3
Wird dies aufgrund der Umstellung auf Set langsamer als Lambda sein?
Ciro Santilli 法轮功 冠状 病 六四 事件 26
32
@ S.Lott, stimmt etwas nicht set(b1) & set(b2)? IMO sein Reiniger, um den Bediener zu verwenden.
GWG
4
Außerdem führt die Verwendung setzu Code, der um Größenordnungen schneller ist. Hier ist ein Beispiel für einen Benchmark®: gist.github.com/andersonvom/4d7e551b4c0418de3160
andersonvom
5
Funktioniert nur, wenn das Ergebnis nicht bestellt werden muss.
Borbag
7
Also ... diese Antwort beantwortet die Frage in keiner Weise, oder? Weil dies jetzt mit verschachtelten Listen funktioniert .
Mayou36
60

Für Leute, die nur den Schnittpunkt zweier Listen suchen, hat der Asker zwei Methoden bereitgestellt:

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]

und

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

print intersect(b1, b2)

Es gibt jedoch eine Hybridmethode, die effizienter ist, da Sie nur eine Konvertierung zwischen Liste / Satz durchführen müssen, im Gegensatz zu drei:

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

Dies wird in O (n) ausgeführt, während seine ursprüngliche Methode zum Listenverständnis in O (n ^ 2) ausgeführt wird.

Zack Burt
quelle
Da "if val in s2" in O (N) ausgeführt wird, ist die vorgeschlagene Komplexität des Code-Snippets ebenfalls O (n ^ 2)
Romeno
8
Der durchschnittliche Fall von "val in s2" ist O (1) gemäß wiki.python.org/moin/TimeComplexity#set - somit ist über n Operationen die erwartete Zeit O (n) (ob die Zeit im ungünstigsten Fall O ist ( n) oder O (n ^ 2) hängen davon ab, ob dieser Durchschnittsfall eine amortisierte Zeit darstellt oder nicht, aber dies ist in der Praxis nicht sehr wichtig.
D Coetzee
2
Die Laufzeit ist O (N), nicht weil sie amortisiert ist, sondern weil die festgelegte Mitgliedschaft im Durchschnitt O (1) ist (zum Beispiel bei Verwendung einer Hash-Tabelle). Dies ist ein großer Unterschied, zum Beispiel weil die amortisierte Zeit garantiert ist.
MiroB
28

Der funktionale Ansatz:

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

und es kann auf den allgemeineren Fall von 1+ Listen angewendet werden

Kugelfisch
quelle
um eine leere Eingabeliste zuzulassen : set(*input_list[:1]).intersection(*input_list[1:]). Iterator-Version ( it = iter(input_list)) : reduce(set.intersection, it, set(next(it, []))). In beiden Versionen müssen nicht alle Eingabelisten zum Festlegen konvertiert werden. Letzteres ist speichereffizienter.
JFS
Verwenden Sie es from functools import reduce, um es in Python 3 zu verwenden. Oder verwenden Sie noch besser eine explizite forSchleife.
TrigonaMinima
27

Version mit reinem Listenverständnis

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

Variante abflachen:

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

Verschachtelte Variante:

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

Der Operator & nimmt den Schnittpunkt zweier Mengen.

{1, 2, 3} & {2, 3, 4}
Out[1]: {2, 3}
aflaisler
quelle
Gut, aber dieses Thema ist für Listen!
Rafa0809
3
Das Ergebnis der Überschneidung zweier Listen ist eine Menge, sodass diese Antwort vollkommen gültig ist.
Spitzmaus
Die Liste kann doppelte Werte enthalten, Sets jedoch nicht.
Diewland
13

Eine pythonische Methode, um den Schnittpunkt zweier Listen zu bestimmen, ist:

[x for x in list1 if x in list2]
Flying_ostrich
quelle
2
Diese Frage bezieht sich auf verschachtelte Listen. Ihre Antwort beantwortet die Frage nicht.
Thomas
8

Sie sollten diesen Code reduzieren (entnommen aus http://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks ). Der Code ist nicht getestet, aber ich bin mir ziemlich sicher, dass er funktioniert:


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

Nachdem Sie die Liste abgeflacht haben, führen Sie die Kreuzung wie folgt aus:


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
quelle
2
Das ist ein schönes Stück Abflachungscode Geo, aber es beantwortet die Frage nicht. Der Fragesteller erwartet das Ergebnis speziell in der Form [[13,32], [7,13,28], [1,6]].
Rob Young
8

Da intersectdefiniert wurde, reicht ein grundlegendes Listenverständnis aus:

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

Verbesserung dank der Bemerkung von S. Lott und der damit verbundenen Bemerkung von TM.:

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

Gegeben:

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

Ich finde, dass der folgende Code gut funktioniert und möglicherweise prägnanter ist, wenn die Set-Operation verwendet wird:

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

Es hat:

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

Bei Bestellung:

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

wir haben:

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

Übrigens, für einen Python-Stil ist auch dieser in Ordnung:

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

Ich weiß nicht, ob ich Ihre Frage zu spät beantworte. Nachdem ich Ihre Frage gelesen hatte, kam ich auf eine Funktion intersect (), die sowohl für Listen als auch für verschachtelte Listen geeignet ist. Ich habe Rekursion verwendet, um diese Funktion zu definieren. Sie ist sehr intuitiv. Hoffe es ist was du suchst:

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

Beispiel:

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

Denken Sie darüber [1,2]nach, sich zu überschneiden [1, [2]]? Das heißt, sind es nur die Zahlen, die Sie interessieren, oder auch die Listenstruktur?

Wenn nur die Zahlen, untersuchen Sie, wie die Listen "abgeflacht" werden, und verwenden Sie dann die set()Methode.

entspannen
quelle
Ich möchte die Struktur der Listen unverändert lassen.
elfuego1
1

Ich suchte auch nach einer Möglichkeit, dies zu tun, und schließlich endete es so:

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
quelle
Wenn ich set.intersection nicht benutze, würde ich diese einfachen Einzeiler auch tun.
Schlachtung98
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
quelle
0

Wir können hierfür festgelegte Methoden verwenden:

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

Um einen Schnittpunkt zu definieren, der die Kardinalität der Elemente korrekt berücksichtigt, verwenden Sie 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
quelle
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]] ?

Hier ist eine Möglichkeit zum Festlegen c3, die keine Sätze umfasst:

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

Wenn Sie jedoch nur eine Zeile verwenden möchten, können Sie dies tun:

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

Es ist ein Listenverständnis innerhalb eines Listenverständnisses, was ein wenig ungewöhnlich ist, aber ich denke, Sie sollten nicht zu viel Mühe haben, ihm zu folgen.

J L
quelle
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]]

Für mich ist das ein sehr eleganter und schneller Weg dorthin :)

Michal
quelle
0

flache Liste kann reduceleicht durch gemacht werden.

Alles was Sie brauchen, um Initialisierer zu verwenden - drittes Argument in der reduceFunktion.

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

Der obige Code funktioniert sowohl für Python2 als auch für Python3, Sie müssen jedoch das Reduktionsmodul als importieren from functools import reduce. Siehe untenstehenden Link für Details.

Raja Sakthiyan
quelle
-1

Einfacher Weg, um Unterschiede und Schnittpunkte zwischen Iterablen zu finden

Verwenden Sie diese Methode, wenn Wiederholung wichtig ist

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
quelle