sort - remove duplicates from list python

Forma pitónica de eliminar duplicados invertidos en la lista.

Question

Tengo una lista de pares:

[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]

y quiero eliminar cualquier duplicado donde

[a,b] == [b,a]

Así que terminamos con solo

[0, 1], [0, 4], [1, 4]

Puedo hacer un bucle interno y externo para verificar el par inverso y adjuntarlo a una lista si ese no es el caso, pero estoy seguro de que hay una forma más pitónica de lograr los mismos resultados.

Answer 1

EDITADO para explicar mejor

Primero ordene cada lista y luego use las claves de los diccionarios para obtener un conjunto único de elementos y la comprensión de la lista.

¿Por qué las tuplas?
Reemplazar listas con tuplas es necesario para evitar el error "irreprimible" al pasar por la función fromkeys ()

my_list = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
tuple_list = [ tuple(sorted(item)) for item in my_list ]
final_list = [ list(item) for item in list({}.fromkeys(tuple_list)) ]

Utilizando OrderedDict incluso conservar el orden de la lista.

from collections import OrderedDict

my_list = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
tuple_list = [ tuple(sorted(item)) for item in my_list ]
final_list = [ list(item) for item in list(OrderedDict.fromkeys(tuple_list)) ]

El código anterior dará como resultado la lista deseada

[[0, 1], [0, 4], [1, 4]]

Answer 2

TL; DR

set(map(frozenset, lst))

Explicación

Si los pares están desordenados lógicamente, se expresan más naturalmente como conjuntos. Sería mejor tenerlos como conjuntos antes de que llegues a este punto, pero puedes convertirlos así:

lst = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
lst_as_sets = map(frozenset, lst)

Y luego, la forma natural de eliminar duplicados en un iterable es convertirlo en un set :

deduped = set(lst_as_sets)

(Esta es la razón principal por la que elegí frozenset en el primer paso. Los set mutables no son hashables, por lo que no se pueden agregar a un set ).

O puede hacerlo en una sola línea como en la sección TL; DR.

Creo que esto es mucho más simple, más intuitivo y que se parece más a la forma en que piensas sobre los datos que a la tarea de clasificar y las tuplas.

Convertir de nuevo

Si, por alguna razón, realmente necesitas una list de list como resultado final, la conversión es trivial:

result_list = list(map(list, deduped))

Pero probablemente sea más lógico dejarlo todo lo más largo posible. Solo puedo pensar en una razón por la que podría necesitar esto, y es la compatibilidad con los códigos / bibliotecas existentes.

Answer 3

Bueno, estoy "revisando el par inverso y adjuntarlo a una lista si ese no es el caso" como dijiste que podrías hacer, pero estoy usando un solo bucle.

x=[[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
out = []
for pair in x:
    if pair[::-1] not in out:
        out.append(pair)
print out

La ventaja sobre las respuestas existentes es que, en mi opinión, es más legible. No se necesita un conocimiento profundo de la biblioteca estándar aquí. Y no hacer un seguimiento de nada complejo. El único concepto que puede ser desconocido para los principiantes es que [::-1] revierte el par.

Sin embargo, el rendimiento es O (n ** 2), así que no lo use si el rendimiento es un problema y / o las listas son grandes.

Answer 4

Podrías usar la función de filter incorporado.

from __future__ import print_function

def my_filter(l):
    seen = set()

    def not_seen(it):
        s = min(*it), max(*it)
        if s in seen:
            return False
        else:
            seen.add(s)
            return True

    out = filter(not_seen, l)

    return out

myList = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
print(my_filter(myList)) # [[0, 1], [0, 4], [1, 4]]

Como complemento, le orientaría hacia el módulo de itertools de Python, que describe una función unique_everseen que hace básicamente lo mismo que antes, pero en una versión perezosa, basada en el generador y eficiente en memoria. Podría ser mejor que cualquiera de nuestras soluciones si está trabajando en arreglos grandes. Aquí está cómo usarlo:

from itertools import ifilterfalse

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen(''AAAABBBCCDAABBB'') --> A B C D
    # unique_everseen(''ABBCcAD'', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

gen = unique_everseen(myList, lambda x: (min(x), max(x))) # gen is an iterator
print(gen) # <generator object unique_everseen at 0x7f82af492fa0>
result = list(gen) # consume generator into a list.
print(result) # [[0, 1], [0, 4], [1, 4]]

No he hecho ninguna métrica para ver quién es más rápido. Sin embargo, la eficiencia de memoria y la complejidad de O parecen mejores en esta versión.

Tiempo mínimo / máximo vs ordenado

La función sorted incorporada podría pasarse a unique_everseen para ordenar elementos en los vectores internos. En su lugar, paso lambda x: (min(x), max(x)) . Como sé que el tamaño del vector es exactamente 2, puedo proceder de esta manera.

Para usar sorted necesitaría pasar lambda x: tuple(sorted(x)) que agrega sobrecarga. No dramáticamente, pero aún así.

myList = [[random.randint(0, 10), random.randint(0,10)] for _ in range(10000)]
timeit.timeit("list(unique_everseen(myList, lambda x: (min(x), max(x))))", globals=globals(), number=20000)
>>> 156.81979029000013
timeit.timeit("list(unique_everseen(myList, lambda x: tuple(sorted(x))))", globals=globals(), number=20000)
>>> 168.8286430349999

Los tiempos se hacen en Python 3, que agrega las variables globals kwarg a timeit.timeit .

Answer 5

Puede ordenar cada par, convertir su lista de pares en un conjunto de tuplas y volver a hacerlas:

l = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
[list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in l]))]
#=> [[0, 1], [1, 4], [0, 4]]

Los pasos pueden ser más fáciles de entender que un largo de una sola línea:

>>> l = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
>>> [sorted(pair) for pair in l]
# [[0, 1], [0, 4], [0, 1], [1, 4], [0, 4], [1, 4]]
>>> [tuple(pair) for pair in _]
# [(0, 1), (0, 4), (0, 1), (1, 4), (0, 4), (1, 4)]
>>> set(_)
# set([(0, 1), (1, 4), (0, 4)])
>>> list(_)
# [(0, 1), (1, 4), (0, 4)]
>>> [list(tpl) for tpl in _]
# [[0, 1], [1, 4], [0, 4]]

Answer 6

Si el orden de los pares y los elementos de pares es importante, crear una nueva lista probando la membresía podría ser el camino a seguir aquí.

pairs = [0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]
no_dups = []
for pair in pairs:
    if not any( all( i in p for i in pair ) for p in no_dups ):
        no_dups.append(pair)

De lo contrario, me gustaría ir con la respuesta de Styvane .

Por cierto, la solución anterior no funcionará en los casos en los que tenga pares coincidentes . Por ejemplo, [0,0] no se agregaría a la lista. Para eso, deberías agregar un cheque adicional:

for pair in pairs:
    if not any( all( i in p for i in pair ) for p in no_dups ) or ( len(set(pair)) == 1 and not pair in no_dups ):
        no_dups.append(pair)

Sin embargo, esa solución no recogerá "pares" vacíos (por ejemplo, [] ). Para eso, necesitarás un ajuste más:

    if not any( all( i in p for i in pair ) for p in no_dups ) or ( len(set(pair)) in (0,1) and not pair in no_dups ):
        no_dups.append(pair)

Se and not pair in no_dups bit and not pair in no_dups para evitar agregar el [0,0] o [] a no_dups dos veces .

Answer 7

Si necesita conservar el orden de los elementos en la lista, puede usar la función sorted y establecer la comprensión con un map como este:

lst = [0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]
data = {tuple(item) for item in map(sorted, lst)}
# {(0, 1), (0, 4), (1, 4)}

O simplemente sin map como este:

data = {tuple(sorted(item)) for item in lst}

Otra forma es usar un frozenset como se muestra here sin embargo, tenga en cuenta que esto solo funciona si tiene elementos distintos en su lista. Porque como set , frozenset siempre contiene valores únicos. Por lo tanto, terminará con un valor único en su lista secundaria (pérdida de datos) que puede no ser lo que desea.

Para generar una lista, siempre puede usar la list(map(list, result)) donde el resultado es un conjunto de tuplas solo en Python-3.0 o más reciente.

Answer 8

Si solo desea eliminar pares invertidos y no desea bibliotecas externas, puede usar una función de generador simple (basada libremente en la itertools "unique_everseen" ):

def remove_reversed_duplicates(iterable):
    # Create a set for already seen elements
    seen = set()
    for item in iterable:
        # Lists are mutable so we need tuples for the set-operations.
        tup = tuple(item)
        if tup not in seen:
            # If the tuple is not in the set append it in REVERSED order.
            seen.add(tup[::-1])
            # If you also want to remove normal duplicates uncomment the next line
            # seen.add(tup)
            yield item

>>> list(remove_reversed_duplicates(a))
[[0, 1], [0, 4], [1, 4]]

La función del generador podría ser una forma bastante rápida de resolver este problema porque las búsquedas de conjuntos son realmente baratas. ¡Este enfoque también mantiene el orden de su lista inicial y solo elimina los duplicados inversos mientras es más rápido que la mayoría de las alternativas!

Si no le importa usar una biblioteca externa y desea eliminar todos los duplicados (invertidos e idénticos), una alternativa es: iteration_utilities.unique_everseen

>>> a = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]

>>> from iteration_utilities import unique_everseen

>>> list(unique_everseen(a, key=set))
[[0, 1], [0, 4], [1, 4]]

Esto verifica si algún elemento tiene el mismo contenido en orden arbitrario (por lo tanto, la key=set ) como otro. En este caso, esto funciona como se esperaba pero también elimina duplicados [a, b] lugar de solo [b, a] ocurrencias. También puede usar key=sorted (como sugieren otras respuestas). El unique_everseen como este tiene una mala complejidad algorítmica porque el resultado de la función key no es hashable y, por lo tanto, la búsqueda rápida se reemplaza por una búsqueda lenta. Para acelerar esto, debe hacer que las claves sean compatibles, por ejemplo, convirtiéndolas en tuplas ordenadas (como sugieren otras respuestas):

>>> from iteration_utilities import chained
>>> list(unique_everseen(a, key=chained(sorted, tuple)))
[[0, 1], [0, 4], [1, 4]]

La chained no es más que una alternativa más rápida a lambda x: tuple(sorted(x)) .

EDITAR: Como lo menciona @ jpmc26, se podría usar frozenset lugar de conjuntos normales:

>>> list(unique_everseen(a, key=frozenset))
[[0, 1], [0, 4], [1, 4]]

Para tener una idea del rendimiento, hice algunas comparaciones de tiempo para las diferentes sugerencias:

>>> a = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]

>>> %timeit list(remove_reversed_duplicates(a))
100000 loops, best of 3: 16.1 µs per loop
>>> %timeit list(unique_everseen(a, key=frozenset))
100000 loops, best of 3: 13.6 µs per loop
>>> %timeit list(set(map(frozenset, a)))
100000 loops, best of 3: 7.23 µs per loop

>>> %timeit list(unique_everseen(a, key=set))
10000 loops, best of 3: 26.4 µs per loop
>>> %timeit list(unique_everseen(a, key=chained(sorted, tuple)))
10000 loops, best of 3: 25.8 µs per loop
>>> %timeit [list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in a]))]
10000 loops, best of 3: 29.8 µs per loop
>>> %timeit set(tuple(item) for item in map(sorted, a))
10000 loops, best of 3: 28.5 µs per loop

Lista larga con muchos duplicados:

>>> import random
>>> a = [[random.randint(0, 10), random.randint(0,10)] for _ in range(10000)]

>>> %timeit list(remove_reversed_duplicates(a))
100 loops, best of 3: 12.5 ms per loop
>>> %timeit list(unique_everseen(a, key=frozenset))
100 loops, best of 3: 10 ms per loop
>>> %timeit set(map(frozenset, a))
100 loops, best of 3: 10.4 ms per loop

>>> %timeit list(unique_everseen(a, key=set))
10 loops, best of 3: 47.7 ms per loop
>>> %timeit list(unique_everseen(a, key=chained(sorted, tuple)))
10 loops, best of 3: 22.4 ms per loop
>>> %timeit [list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in a]))]
10 loops, best of 3: 24 ms per loop
>>> %timeit set(tuple(item) for item in map(sorted, a))
10 loops, best of 3: 35 ms per loop

Y con menos duplicados:

>>> a = [[random.randint(0, 100), random.randint(0,100)] for _ in range(10000)]

>>> %timeit list(remove_reversed_duplicates(a))
100 loops, best of 3: 15.4 ms per loop
>>> %timeit list(unique_everseen(a, key=frozenset))
100 loops, best of 3: 13.1 ms per loop
>>> %timeit set(map(frozenset, a))
100 loops, best of 3: 11.8 ms per loop


>>> %timeit list(unique_everseen(a, key=set))
1 loop, best of 3: 1.96 s per loop
>>> %timeit list(unique_everseen(a, key=chained(sorted, tuple)))
10 loops, best of 3: 24.2 ms per loop
>>> %timeit [list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in a]))]
10 loops, best of 3: 31.1 ms per loop
>>> %timeit set(tuple(item) for item in map(sorted, a))
10 loops, best of 3: 36.7 ms per loop

Así que las variantes con remove_reversed_duplicates , unique_everseen ( key=frozenset ) y set(map(frozenset, a)) parecen ser, con mucho, las soluciones más rápidas. Cuál depende de la longitud de la entrada y el número de duplicados.

Answer 9

Una solución fácil y desagradable :

pairs = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
s=set()
for p in pairs:
    # Lists are unhashable so make the "elements" into tuples
    p = tuple(p)
    if p not in s and p[::-1] not in s:
        s.add(p)

print s