Schnittpunkt zweier verschachtelter Listen finden?

Lesezeit: 4 Minuten

elfuego1

Ich weiß, wie man eine Schnittmenge von zwei flachen 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?

Verwandt

Reduzieren einer flachen Liste in Python

Was wäre Ihr Schnittpunkt für c1 schneiden c2? Möchten Sie einfach herausfinden, ob c1 in c2 ist? Oder möchten Sie alle Elemente in c1 finden, die irgendwo in c2 vorkommen?

– Brian R. Bondy

13. März 2009 um 13:59 Uhr
Lesen Dies und im Dolmetscher spielen.

– Pithikos

20. Januar 2015 um 10:40 Uhr

S. Lott

Sie müssen keine Schnittmenge definieren. Es ist schon ein erstklassiges 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])

Wird dies aufgrund der Konvertierung in set langsamer als Lambda sein?

– Ciro Santilli Путлер Капут 六四事

26. März 2014 um 4:33 Uhr
@S.Lott, irgendetwas stimmt nicht mit set(b1) & set(b2)? IMO ist es sauberer, den Operator zu verwenden.

– jds

19. Februar 2015 um 23:18 Uhr
Außerdem verwenden set wird zu Code führen, der um Größenordnungen schneller ist. Hier ist ein Beispiel-Benchmark®: gist.github.com/andersonvom/4d7e551b4c0418de3160

– andersonvom

25. November 2015 um 15:33 Uhr
Funktioniert nur, wenn das Ergebnis nicht bestellt werden muss.

– Borbag

17. August 2017 um 10:40 Uhr
Also … diese Antwort beantwortet in keiner Weise die Frage, oder? Denn das funktioniert jetzt mit verschachtelt Listen.

– Mayou36

6. September 2017 um 17:21 Uhr

Brian R. Bondy

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]

Bei Python3 filter gibt statt ein Iterable zurück listalso müssen Sie wickeln filter telefoniert mit list():

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 sich in der Quellenliste c1 befindet. Das Listenverständnis wird für jede Unterliste in c2 ausgeführt.

Sie können verwenden filter(set(c1).__contains__, sublist) für Effizienz. Übrigens, der Vorteil dieser Lösung ist, dass filter() behält Zeichenfolgen- und Tupeltypen bei.

– jfs

14. März 2009 um 10:46 Uhr
Ich mag diese Methode, aber ich bekomme ein leeres ” in meiner Ergebnisliste

– Jonathan Ong

7. Dezember 2011 um 21:35 Uhr
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 – Слава Україні

29. Mai 2016 um 5:01 Uhr
Dies liest sich besser IMO mit verschachtelten Verständnissen: c3 = [[x for x in sublist if x in c1] for sublist in c2]

– Erich

20. August 2016 um 19:06 Uhr

Für Leute, die nur den Schnittpunkt zweier Listen finden möchten, bietet der Asker zwei Methoden:

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)

Aber es gibt eine hybride Methode, die effizienter ist, weil Sie nur eine Umwandlung zwischen list/set machen 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, die das Listenverständnis beinhaltet, in O (n ^ 2) ausgeführt wird.

Da “if val in s2” in O(N) läuft, ist die vorgeschlagene Code-Snippet-Komplexität ebenfalls O(n^2)

– Einhorn

21. März 2013 um 7:42 Uhr
Der durchschnittliche Fall von „val in s2“ ist O(1) gemäß wiki.python.org/moin/TimeComplexity#set – also über n Operationen ist die erwartete Zeit O(n) (ob die Worst-Case-Zeit O(n) oder O(n^2) ist, hängt davon ab, ob dieser Durchschnittsfall eine amortisierte Zeit darstellt oder nicht, aber das ist es nicht in der Praxis sehr wichtig).

– Chiara Coetzee

1. November 2013 um 23:20 Uhr
Die Laufzeit ist O (N), nicht weil sie amortisiert wird, sondern weil die Satzmitgliedschaft im Durchschnitt O (1) ist (z. B. bei Verwendung einer Hash-Tabelle), ist dies ein großer Unterschied, z. B. weil die amortisierte Zeit garantiert ist.

– miroB

4. Dezember 2017 um 20:27 Uhr

Kugelfisch

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

Reine Listenverständnisversion

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

Flatten-Variante:

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

Jean-Francois Fabre

Der &-Operator nimmt den Schnittpunkt zweier Mengen.

{1, 2, 3} & {2, 3, 4}
Out[1]: {2, 3}

petezurich

Eine pythonische Art, den Schnittpunkt von 2 Listen zu nehmen, ist:

[x for x in list1 if x in list2]

Bei dieser Frage geht es um verschachtelte Listen. Ihre Antwort beantwortet die Frage nicht.

– Thomas

18. November 2019 um 12:19 Uhr

11125100cookie-checkSchnittpunkt zweier verschachtelter Listen finden?

#aufführen #Python #Überschneidung