Python Link Unterlisten zusammen, dass Unterlisten kein Element in list2 haben und haben ein Element in list3

Question

I mit den gleichen Elementen zusammen und alle Elementen in Unterlisten zu einer Gruppe von Unterlisten brauchen kein Element in list2 und haben ein Element in list3 Zum Beispiel:

list1 = [[1,4],[4,5],[5,7],[6,7],[9,7],[10,9],[8,10],[8,11],[8,13],[13,15]] 
list2 = [7,8] 
list3 = [1,6,11,13] 

würde ich einen Link [4,5] und [1,4] zusammen, da sie beide 1 gleiche Zahl enthalten und die beiden in [1,4,5] verbinden würde und sie enthalten 1 in list3 und enthalten nicht 7 in list2

So

nach der Linksetzung sollte die neue Liste wie:

new_list1 = [[1,4,5],[6],[11],[13,15]] 

IE: es nicht gleiche Anzahl in einer Unterliste sein soll und Ordnung ist nicht wichtig.

Ein längeres Beispiel:

list1 = [[1,4],[4,5],[5,7],[6,7],[9,7],[10,9],[8,10],[8,11],[8,13],[6,8],[20,2],[20,3],[11,14],[14,16],[13,15]] 
list2 = [7,8,20] 
list3 = [1,2,3,16,15] 

nach der Linksetzung wäre es

new_list = [[1,4,5],[2,3],[11,14,16],[13,15]] 

Wie kann dies in einer allgemeinen Weise getan werden?

EDIT Der endgültige Algorithmus der folgenden drei grundlegenden Schritte umfassen sollte:

1. Entfernen Sie alle Elemente aller Teillisten von list1, die in list2
2. Mitglied werden alle Unterlisten enthalten sind, list1 mit gemeinsamen Elementen
3. Entfernen Sie alle Unterlisten von list1, die keine Elemente von list3
enthalten

Answer 1

Hier ist mein nehmen auf sie, wenn Thomas Kühn richtig verwaltet Ihre Gedanken zu lesen:

def subgroup_join(data, exclude, include): 
    exclude = set(exclude) # turn into set for faster lookup/compare 
    include = set(include) # turn into set for faster lookup/compare 
    data = [set(element) - exclude for element in data] # remove excluded elements 
    results = [set()] # init with an empty set 
    for element in data: # loop through our remaining elements 
     groups = [] # store elements/current results filtered by exclude list 
     ignore_element = False # flag if we should add the element as a standalone 
     for result in results: # go through each subgroup in the results 
      if element & result: # if the current element has common items with the result 
       result |= element # ... concatenate both into a subgroup 
       ignore_element = True 
      groups.append(result) # add the current result subgroup 
     if not ignore_element: # add only if the element wasn't concatenated 
      groups.append(element) # add the current element 
     results = groups # our element store becomes our new results set 
    return sorted([sorted(res) for res in results if result & include]) # sort & return 

Wie für Tests:

list1 = [[1, 4], [4, 5], [5, 7], [6, 7], [7, 8], [9, 7], [10, 9], [8, 10], [8, 11], [8, 13], [13, 15]] 
list2 = [7, 8] 
list3 = [1, 6, 11, 13] 

print(subgroup_join(list1, list2, list3)) 
# prints: [[1, 4, 5], [6], [11], [13, 15]] 

list1 = [[1, 4], [4, 5], [5, 7], [6, 7], [9, 7], [10, 9], [8, 10], [8, 11], [8, 13], [6, 8], [20, 2], [20, 3], [11, 14], [14, 16], [13, 15]] 
list2 = [7, 8, 20] 
list3 = [1, 2, 3, 16, 15] 

print(subgroup_join(list1, list2, list3)) 
# prints: [[1, 4, 5], [2], [3], [11, 14, 16], [13, 15]] 

Dies ist wahrscheinlich der schnellste Ansatz vom präsentiert, aber wieder - es stimmt nicht genau mit Ihren Beispielen überein - überprüfen Sie das letzte Ergebnis und die Ergebnisse [2] und [3].

UPDATE:

Wenn es um Leistung geht, die zweite Liste Gruppe mit:

zwer_join - 100,000 loops: 2.849 s; per loop: 28.399 µs 
kuhn_join - 100,000 loops: 3.071 s; per loop: 30.706 µs 
nuag_join - 1,000 loops: 15.82 s; per loop: 15.819 ms (had to reduce the number of loops) 

Answer 2

Zuerst beginnen Sie mit dem Schreiben Ihrer join Funktion. Ich habe die zweite Liste hinzugefügt, um unerwünschte Elemente zu entfernen.

Dann iterieren Sie durch Ihre beigefügte Liste und sehen, ob eines der Elemente derzeit in Ihrer Liste ist. Wenn ja, suchen Sie nach dem Ort, an dem sie hingehören, dann fügen Sie Elemente hinzu (Ich habe set verwendet, um doppelte zu vermeiden).

Die Ausgänge werden am Ende ausgegeben.

def join(list1, list2): 
    l = [] 
    for ee in list1: 
     # We consider here that list1 only have pairs 
     if ee[0] not in list2 and ee[1] not in list2: 
      flat_l = [x for e in l for x in e] 
      if ee[0] in flat_l or ee[1] in flat_l: 
       for i, e in enumerate(l): 
        if ee[0] in e: 
         l[i].append(ee[1]) 
        if ee[1] in e: 
         l[i].append(ee[0]) 
      else: 
       l.append(ee) 
    return l 

def f(list1,list2,list3): 
    l = [[e] for e in list3] 
    list1 = join(list1, list2) 
    for ee in list1: 
     flat_l = [x for e in l for x in e] 
     for e in ee: 
      if e in flat_l: 
       for i in range(len(l)): 
        if e in l[i]: 
         l[i] = list(set(l[i]+ee)) 
    print(l) 

list1 = [[1,4],[4,5],[5,7],[6,7],[9,7],[10,9],[8,10],[8,11],[8,13],[13,15]] 
list2 = [7,8] 
list3 = [1,6,11,13] 

f(list1,list2,list3) 
# [[1, 4, 5], [6], [11], [13, 15]] 

list1 = [[1,4],[4,5],[5,7],[6,7],[9,7],[10,9],[8,10],[8,11],[8,13],[6,8],[20,2],[20,3],[11,14],[14,16],[13,15]] 
list2 = [7,8,20] 
list3 = [1,2,3,16,15] 

f(list1,list2,list3) 
# [[1, 4, 5], [2], [3], [16, 11, 14], [13, 15]] 

Answer 3

Dieser Code sollte die Arbeit machen:

list1 = [[1,4],[4,5],[5,7],[6,7],[9,7],[10,9],[8,10],[8,11],[8,13],[6,8],[20,2],[20,3],[11,14],[14,16],[13,15]] 
list2 = [7,8,20] 
list3 = [1,2,3,16,15] 

list1a = [set(l) for l in list1] 
#removing elements from list1 that contain numbers of list2: 
for x in list2: 
    for l in list(list1a): 
     if x in l: 
      l.remove(x) 

#joining sub-lists in list1: 
list1b = [set(l) for l in list1a] 
list1c = [] 
while list1b: 
    s1 = list1b.pop(0) 
    for s2 in list(list1b): 
     if s1 & s2: 
      s1 |= s2 
      list1b.remove(s2) 
    list1c.append(s1) 

#generating final list with only sub-lists that contain elements of list2 
list1_new = sorted([sorted(list(s)) for s in list1c if s & set(list3)]) 

Für das erste Beispiel, ergibt dies:

[[1, 4, 5], [6], [11], [13, 15]] 

und für das zweite Beispiel

[[1, 4, 5], [2], [3], [11, 14, 16], [13, 15]] 

Hope this hilft.