Ich habe drei Sets:
%Vor%Ich möchte eine Funktion, die True zurückgibt, wenn jeder Satz in der Liste sich mit mindestens einem anderen Satz in der Liste überschneidet. Gibt es dafür ein eingebautes oder einfaches Listenverständnis?
Es ist ein wenig ausführlich, aber ich denke, es ist eine ziemlich effiziente Lösung. Es nutzt die Tatsache, dass, wenn zwei Sätze sich schneiden, wir sie beide als verbunden markieren können. Dies geschieht, indem eine Liste von Flags so lange wie die Liste der Sets beibehalten wird. Wenn i gesetzt und j sich überschneiden gesetzt wird, wird das Flag für beide gesetzt. Anschließend wird die Liste der Sätze übersprungen und nur eine Schnittmenge für Mengen gesucht, die noch nicht geschnitten wurden. Nachdem ich die Kommentare gelesen habe, denke ich, dass @Victor davon sprach.
Ich entschied, dass eine leere Liste von Mengen verbunden ist (Wenn Sie ein Element der Liste erzeugen, kann ich ein Element erzeugen, das es schneidet;). Eine Liste mit nur einem Element wird trivial getrennt. In beiden Fällen ist eine Zeile zu ändern, wenn Sie nicht zustimmen.
Hier ist eine effizientere (wenn auch viel kompliziertere) Lösung, die eine lineare Anzahl von Schnittpunkten und eine Anzahl von Vereinigungen der Ordnung O (n * log (n)) ausführt, wobei n die Länge von Beachten Sie, dass diese Lösung nur mit Python & gt; = 2.6 funktioniert. s :
Wie immer möchte ich die unvermeidliche itertools Lösung geben; -)
Das ist wirklich faul und macht nur die notwendigen Überschneidungen. Es kann auch ein sehr verwirrender und unleserlicher oneliner sein ;-)
Um Ihre Frage zu beantworten, nein, es gibt kein integriertes oder einfaches Listenverständnis, das das tut, was Sie wollen. Hier ist eine weitere itertools basierte Lösung, die sehr effizient ist - überraschend etwa doppelt so schnell wie @ THC4k itertools antwortet mit groupby() in Timing-Tests mit Ihrer Beispieleingabe. Es könnte wahrscheinlich ein bisschen weiter optimiert werden, ist aber wie dargestellt sehr gut lesbar. Wie @AaronMcSmooth habe ich willkürlich entschieden, was zurückgegeben werden soll, wenn keine oder nur ein Satz in der Eingabeliste vorhanden ist.
Diese Strategie ist wahrscheinlich nicht so effizient wie @ Victors Vorschlag, könnte aber effizienter sein als jchls Antwort aufgrund der verstärkten Verwendung der Mengenarithmetik ( union ).
Dies kann je nach Verteilung der Sets zu einer besseren Leistung führen.
%Vor%