¿Cómo comparar eficientemente dos listas desordenadas (no conjuntos)?
a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]
a y b deben considerarse iguales, porque tienen exactamente los mismos elementos, solo que en diferente orden.
La cuestión es que mis listas reales consistirán en objetos (mis instancias de clase), no en números enteros.
Aceptado
O(n) : El método Counter() es mejor (si sus objetos son hash):
def compare(s, t):
return Counter(s) == Counter(t)
O(n log n) : el método sorted() es el siguiente mejor (si sus objetos se pueden ordenar):
def compare(s, t):
return sorted(s) == sorted(t)
O(n * n) : si los objetos no son hash ni ordenables, puedes usar la igualdad:
def compare(s, t):
t = list(t) # make a mutable copy
try:
for elem in s:
t.remove(elem)
except ValueError:
return False
return not t
Puedes ordenar ambos:
sorted(a) == sorted(b)
Una clasificación por conteo también podría ser más eficiente (pero requiere que el objeto sea hash).
>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True
