in der Liste der Listen

Question

Ich habe zwei Listen von Listen:

a = [[0, 1, 5], [2], [3], [4], [6, 7], [8, 9, 10, 11], [12], [13], [14], [15]] 
b = [[0, 1], [2, 3], [4], [5], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

Wie kann ich die maximale Überlappung zwischen den Werten der Listen finden und bauen eine neue Liste von Listen mit dieser maximalen Überlappung. Mit anderen Worten, ich bin auf der Suche nach einer Funktion f, die die Listengrößen durch Zusammenführen von Listen mit Überlappung maximiert.

Das gewünschte Ergebnis der Funktion f für dieses Beispiel wäre:

f(a,b) = [[0, 1, 5], [2, 3], [4], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

Answer 1

Sie eine Variante der disjoint-set structure verwenden kann, dieses Problem zu lösen: für jede Liste [a,b,c] Sie mita mit b und a vereinigen c. Sie tun dies für beide Listen und leiten dann die resultierenden Wurzeln ab.

Here gibt es ein einfach disjunct-Set Algorithmus, den wir ändern können:

from collections import defaultdict 

def parent(u,mapping): 
    if mapping[u] == u: 
     return u 
    mapping[u] = parent(mapping[u],mapping) 
    return mapping[u] 

def relation(array,mapping=None): 
    if mapping is None: 
     mapping = {} 

    for e in array: 
     if len(e) > 0: 
      u = e[0] 
      if u not in mapping: 
       mapping[u] = u 
      for v in e[1:]: 
       if v not in mapping: 
        mapping[v] = v 
       mapping[parent(u,mapping)] = parent(v,mapping) 
    return mapping 

def f(a,b): 
    mapping = {} 
    relation(a,mapping) 
    relation(b,mapping) 

    results = defaultdict(set) 
    for u in mapping.keys(): 
     results[parent(u,mapping)].add(u) 
    return [list(x) for x in results.values()]

(fett gedruckt hinzugefügt für die semantischen Differenzen mit dem ursprünglichen union-set-Algorithmus).

Dies erzeugt:

>>> f(a,b) 
[[2, 3], [4], [0, 1, 5], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

Das Ergebnis ist nicht sortiert, da wir mit einer Reihe arbeiten. Trotzdem können Sie leicht jedes Tupel auf dem ersten Element sortieren, wenn Sie durch f zu verändern wollen:

def f(a,b): 
    mapping = {} 
    relation(a,mapping) 
    relation(b,mapping) 

    results = defaultdict(set) 
    for u in mapping.keys(): 
     results[parent(u,mapping)].add(u) 
    return sorted([list(x) for x in results.values()],key=lambda t:t[0])

, die produziert:

>>> f(a,b) 
[[0, 1, 5], [2, 3], [4], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

Das schöne an dieser Lösung ist, dass es funktioniert auch Wenn es Überlappung in a oder b selbst gibt, und Sie können die Lösung leicht verallgemeinern, um mit einer beliebigen Anzahl von Listen zu arbeiten (zum Beispiel a, b und c).

Answer 2

Wenn ich es richtig verstanden, die Folgenden wird es tun:

[l for l in a if not any(all(x in l2 for x in l) for l2 in b)] + 
[l for l in b if not any(all(x in l2 for x in l) for l2 in a)] + 
[l for l in a if l in b] 

Der erste Term alle Listen in a ergibt, die nicht Teil der Listen in b sind; der zweite Ausdruck ergibt alle Listen in b, die Anmerkungsteil wenn Listen in a sind; Der dritte Term ergibt alle Listen, die sowohl in a als auch in b stehen.

Für Ihr Beispiel ergibt sich folgendes Ergebnis:

[[0, 1, 5], [2, 3], [13, 14], [4], [6, 7], [8, 9, 10, 11], [12], [15]]