Determine si 2 listas tienen los mismos elementos, independientemente del orden?

Question

Disculpe la simple pregunta, pero me está costando encontrar la respuesta.

Cuando comparo 2 listas, quiero saber si son "iguales" en que tienen los mismos contenidos, pero en diferente orden.

Ex:

x = ['a', 'b'] 
y = ['b', 'a'] 

Quiero x == y para evaluar a True.

Answer 1

Simplemente puede comprobar si los conjuntos múltiples con los elementos de X e Y son iguales:

import collections 
collections.Counter(x) == collections.Counter(y) 

Esto requiere que los elementos a ser hashable; el tiempo de ejecución estará en O(n), donde n tiene el tamaño de las listas.

Si los elementos también son únicos, también se puede convertir a los conjuntos (el mismo tiempo de ejecución asintótica, puede ser un poco más rápido en la práctica):

set(x) == set(y) 

Si los elementos no son hashable, pero se puede ordenar, otro alternativa (en tiempo de ejecución O(n log n)) es

sorted(x) == sorted(y) 

Si los elementos no son ni hashable ni sortable puede utilizar la siguiente función auxiliar. Tenga en cuenta que será bastante lento (O(n²)) y, en general, se debe usar no fuera de la caja esotérica de elementos no aptos para el ajuste y no orientables.

def equal_ignore_order(a, b): 
    """ Use only when elements are neither hashable nor sortable! """ 
    unmatched = list(b) 
    for element in a: 
     try: 
      unmatched.remove(element) 
     except ValueError: 
      return False 
    return not unmatched 

Answer 2

Determinar si 2 listas tienen los mismos elementos, independientemente del orden?

inferir de tu ejemplo:

x = ['a', 'b'] 
y = ['b', 'a'] 

que no se repetirán los elementos de las listas (que son únicos), así como hashable (que cuerdas y otros ciertos objetos inmutables son pitón) , la respuesta más directa y computacionalmente eficiente usa conjuntos integrados de Python, (que son semánticamente semejantes a conjuntos matemáticos de los que puedes haber aprendido en la escuela).

set(x) == set(y) # prefer this if elements are hashable 

En el caso de que los elementos son hashable, pero no único, la collections.Counter también trabaja semánticamente como un conjunto múltiple, pero que es mucho más lento:

from collections import Counter 
Counter(x) == Counter(y) 

prefieren utilizar sorted:

sorted(x) == sorted(y) 

si los elementos pueden ordenarse. Esto explicaría las circunstancias no únicas o no manejables, pero esto podría ser mucho más lento que usar conjuntos.

experimento empírico

un experimento empírico concluye que se debe preferir set, entonces sorted. Solo opte por Counter si necesita otras cosas como conteos o uso posterior como multiset.

Primera configuración:

import timeit 
import random 
from collections import Counter 

data = [str(random.randint(0, 100000)) for i in xrange(100)] 
data2 = data[:]  # copy the list into a new one 

def sets_equal(): 
    return set(data) == set(data2) 

def counters_equal(): 
    return Counter(data) == Counter(data2) 

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2) 

y pruebas:

>>> min(timeit.repeat(sets_equal)) 
13.976069927215576 
>>> min(timeit.repeat(counters_equal)) 
73.17287588119507 
>>> min(timeit.repeat(sorted_lists_equal)) 
36.177085876464844 

Y vemos que la comparación de conjuntos es la solución más rápida, y la comparación de listas ordenadas es el segundo más rápido.

Answer 3

Esto parece funcionar, aunque posiblemente engorroso para listas grandes.

>>> A = [0, 1] 
>>> B = [1, 0] 
>>> C = [0, 2] 
>>> not sum([not i in A for i in B]) 
True 
>>> not sum([not i in A for i in C]) 
False 
>>> 

Sin embargo, si cada lista obligada contiene todos los elementos de otro entonces el código anterior es problemático.

>>> A = [0, 1, 2] 
>>> not sum([not i in A for i in B]) 
True 

El problema surge cuando len(A) != len(B) y, en este ejemplo, len(A) > len(B). Para evitar esto, puede agregar una declaración más.

>>> not sum([not i in A for i in B]) if len(A) == len(B) else False 
False 

Una cosa más, como punto de referencia con mi solución timeit.repeat, en las mismas condiciones utilizadas por Aaron Hall en su puesto. Como se sospecha, los resultados son decepcionantes. Mi método es el último. set(x) == set(y) es.

>>> def foocomprehend(): return not sum([not i in data for i in data2]) 
>>> min(timeit.repeat('fooset()', 'from __main__ import fooset, foocount, foocomprehend')) 
25.2893661496 
>>> min(timeit.repeat('foosort()', 'from __main__ import fooset, foocount, foocomprehend')) 
94.3974742993 
>>> min(timeit.repeat('foocomprehend()', 'from __main__ import fooset, foocount, foocomprehend')) 
187.224562545 

Answer 4

Como se mencionó en los comentarios anteriores, el caso general es un dolor. Es bastante fácil si todos los artículos son lavables o todos los artículos son ordenables. Sin embargo, recientemente tuve que intentar resolver el caso general. Aquí está mi solución. Me di cuenta después de publicar que este es un duplicado de una solución anterior que perdí en el primer pase. De todos modos, si usas slices en lugar de list.remove() puedes comparar secuencias inmutables.

def sequences_contain_same_items(a, b): 
    for item in a: 
     try: 
      i = b.index(item) 
     except ValueError: 
      return False 
     b = b[:i] + b[i+1:] 
    return not b