Sortieren einer Untergruppe einer Python-Liste, um die gleichen relativen Reihenfolge wie in anderen Liste haben

Question

mit So eine Liste b = [b1, b2, b3] sagen, ich möchte eine Liste a so sortieren können, dass alle bi ‚s, die auch in a existieren haben die gleiche relative Reihenfolge wie in b - den Rest der a Elemente allein lassen. So

a = [ b1, x, b3, y, b2] -> [ b1, x, b2, y, b3] 
a = [ b1, x, b2, y, b3] -> no change 
a = [ b1, x, y, b2]  -> no change 
a = [ b3, x, b1, y, b2] -> [ b1, x, b2, y, b3] 

b kann natürlich ein Tupel oder jede andere geordnete Struktur sein. Was ich ist nach oben kam mit

bslots = dict((x, a.index(x)) for x in a if x in b) 
bslotsSorted = sorted(bslots.keys(), key=lambda y: b.index(y)) 
indexes = sorted(bslots.values()) 
for x,y in zip(bslotsSorted, indexes): 
    a[y] = x 

plump und O (n^2)

Answer 1

• zuerst ein Wörterbuch erstellen Elementen aus b mit dem der Schlüssel, der Punkt und Wert sein Index ist, werden wir Verwenden Sie dies, um die übereinstimmenden Elemente in a später zu sortieren.

• Jetzt Filter Artikel aus a, die in diesem dict vorhanden sind, dict bietet O (1) lookup.

• Sortieren Sie nun diese Liste gefilterter Elemente und konvertieren Sie sie in einen Iterator.

• Wiederholen Sie die Schleife erneut mit a und überprüfen Sie für jedes Element, ob in dict vorhanden ist, und rufen Sie dann den Wert des Iterators ab, andernfalls verwenden Sie ihn unverändert.

def solve(a, b): 
    dct = {x: i for i, x in enumerate(b)} 
    items_in_a = [x for x in a if x in dct] 
    items_in_a.sort(key=dct.get) 
    it = iter(items_in_a) 
    return [next(it) if x in dct else x for x in a] 
... 
>>> b = ['b1', 'b2', 'b3'] 
>>> a = [ 'b1', 'x', 'b3', 'y', 'b2'] 
>>> solve(a, b) 
['b1', 'x', 'b2', 'y', 'b3'] 
>>> a = [ 'b1', 'x', 'b2', 'y', 'b3'] 
>>> solve(a, b) 
['b1', 'x', 'b2', 'y', 'b3'] 
>>> a = [ 'b1', 'x', 'y', 'b2'] 
>>> solve(a, b) 
['b1', 'x', 'y', 'b2'] 
>>> a = [ 'b3', 'x', 'b1', 'y', 'b2'] 
>>> solve(a, b) 
['b1', 'x', 'b2', 'y', 'b3'] 

Gesamtzeitkomplexität max von (O(len(a)), O(len(b)), O(items_in_a_length log items_in_a_length) sein wird.

Answer 2

Die angenommene Antwort beantwortet die Frage, wie gefragt, aber mein tatsächliches Problem war ein bisschen restriktiver - nämlich würde ich gerne Artikel in den gleichen relativen Positionen in a so viel wie möglich zu halten. So ist die akzeptierte Antwort (und mein ursprünglicher Versuch) würde:

b = [ A, E, B ] 
a = [ A, B, C, D, E, Z] -> [ A, E, C, D, B, Z ] 

Ich mag nur „sprudeln“ der Out-of-Order-Artikel, so dass sie wie einige ihrer Vorfahren wie möglich verlieren: [ A, B, C, D, E, Z ] -> [ A, C, D, E, B, Z ]. Beachten Sie, dass E bisher die Vorfahren C und D verlieren würde, während B jetzt nur noch B verliert. Abgeprüft:

def reorder(a, b): 
    bb = b[:] 
    b_in_a = [x for x in a if x in set(b)] 
    w = dict((x, i) for i, x in enumerate(a)) 
    while b_in_a: 
     for i, (ordered, current) in enumerate(zip(bb, b_in_a)): 
      if ordered != current: 
       for j, x in enumerate(b_in_a[i:]): 
        if x == ordered: break 
        to = w[ordered] + 1 + j 
        w = dict((x,i if i < to else i+1) for x,i in w.iteritems()) 
        w[x] = to # bubble them up ! 
       b_in_a.remove(ordered) 
       bb = bb[i + 1:] 
       b_in_a = b_in_a[i:] 
       break 
     else: 
      break 
    aa = a[:] 
    a.sort(key=w.__getitem__) 
    print aa, '-', b, ' -> ', a 

# ['A', 'B', 'C', 'D', 'E'] - ['A', 'E', 'B'] -> ['A', 'C', 'D', 'E', 'B'] 
# ['A', 'B', 'C', 'D', 'E', 'F'] - ['A', 'E', 'C', 'B'] -> ['A', 'D', 'E', 'C', 'B', 'F']