Rimozione di elementi duplicati da un elenco Python contenente elementi non selezionabili conservando l'ordine?

Question

Ho un datastructure come questo:

[ 
[('A', '1'), ('B', '2')], 
[('A', '1'), ('B', '2')], 
[('A', '4'), ('C', '5')] 
] 

e voglio ottenere questo:

[ 
[('A', '1'), ('B', '2')], 
[('A', '4'), ('C', '5')] 
] 

C'è un buon modo di fare questo, mantenendo ordine come indicato?

Comandi per copia-incolla:

sample = [] 
sample.append([('A', '1'), ('B', '2')]) 
sample.append([('A', '1'), ('B', '2')]) 
sample.append([('A', '4'), ('C', '5')]) 

Answer 1

Questo è un po 'famosa domanda che era ben risposto da un famoso Pythonista molto tempo fa: http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/

Se si può assumere pari record sono adiacenti, non v'è una ricetta nella itertools docs:

from operator import itemgetter 
from itertools import groupby, imap 

def unique_justseen(iterable, key=None): 
    "List unique elements, preserving order. Remember only the element just seen." 
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B 
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D 
    return imap(next, imap(itemgetter(1), groupby(iterable, key))) 

Se si può solo supporre elementi ordinabili, ecco una variante con il bisect m odule. Dati gli n ingressi con r valori univoci, il suo passo di ricerca costa O (n log r). Se viene trovato un nuovo valore univoco, viene inserito nell'elenco visto per un costo di O (r * r).

from bisect import bisect_left, insort 

def dedup(seq): 
    'Remove duplicates. Preserve order first seen. Assume orderable, but not hashable elements' 
    result = [] 
    seen = [] 
    for x in seq: 
     i = bisect_left(seen, x) 
     if i == len(seen) or seen[i] != x: 
      seen.insert(i, x) 
      result.append(x) 
    return result 

Answer 2

Ecco una variante ordine-preserving del genere/linguaggio unico. Ciò ti darà prestazioni O (n log n), a condizione che i tuoi articoli siano almeno ordinabili.

def unique(a): 
    indices = sorted(range(len(a)), key=a.__getitem__) 
    indices = set(next(it) for k, it in 
        itertools.groupby(indices, key=a.__getitem__)) 
    return [x for i, x in enumerate(a) if i in indices] 

Esempio (con gli oggetti hashable per semplicità):

>>> a = ['F', 'J', 'B', 'F', 'V', 'A', 'E', 'U', 'B', 'U', 'Z', 'K'] 
>>> unique(a) 
['F', 'J', 'B', 'V', 'A', 'E', 'U', 'Z', 'K']