Determina se 2 elenchi hanno gli stessi elementi, indipendentemente dall'ordine?

Question

Ci scusiamo per la semplice domanda, ma ho difficoltà a trovare la risposta.

Quando paragono 2 elenchi, voglio sapere se sono "uguali" in quanto hanno gli stessi contenuti, ma in ordine diverso.

Es:

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

voglio x == y per valutare a True.

Answer 1

Si può semplicemente controllare se i multinsiemi con gli elementi di x ed y sono uguali:

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

Questo richiede gli elementi per essere hashable; il runtime sarà in O(n), dove n è la dimensione degli elenchi.

Se gli elementi sono anche unico, è anche possibile convertire in set (stesso tempo di esecuzione asintotico, può essere un po 'più veloce, in pratica):

set(x) == set(y) 

Se gli elementi non sono hashable, ma ordinabile, un altro alternativa (runtime in O(n log n)) è

sorted(x) == sorted(y) 

Se gli elementi non sono né hashable né ordinabile è possibile utilizzare la seguente funzione di supporto. Si noti che sarà piuttosto lento (O(n²)) e generalmente dovrebbe essere non essere utilizzato al di fuori del caso esoterico di elementi non selezionabili e non selezionabili.

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

Determinare se 2 liste hanno gli stessi elementi, a prescindere dalla fine?

Dedurre dal vostro esempio:

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

che gli elementi delle liste non saranno ripetuti (sono unici), così come hashable (che stringhe e altri determinati oggetti Python immutabili sono) , la risposta più diretta ed efficiente dal punto di vista computazionale utilizza i set predefiniti di Python, (che sono semanticamente come set matematici di cui potresti aver imparato a scuola).

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

Nel caso in cui gli elementi sono hashable, ma non univoco, il collections.Counter funziona anche semanticamente come multinsieme, ma che è molto più lento:

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

preferisce utilizzare sorted:

sorted(x) == sorted(y) 

se gli elementi sono ordinabili. Ciò spiegherebbe le circostanze non univoche o non-lavabili, ma potrebbe essere molto più lento rispetto all'uso dei set.

Esperimento empirica

Un esperimento empirico conclude che si dovrebbe preferire set, quindi sorted. Optate solo per Counter se avete bisogno di altre cose come conteggi o ulteriore utilizzo come multiset.

Prima impostazione:

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) 

e test:

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

Così vediamo che il confronto insiemi è la soluzione più veloce, e confrontando gli elenchi ordinati è il secondo più veloce.

Answer 3

Questo sembra funzionare, sebbene possibilmente ingombrante per elenchi di grandi dimensioni.

>>> 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 
>>> 

Tuttavia, se ciascun elenco must contiene tutti gli elementi di altri quindi il codice precedente è problematico.

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

Il problema sorge quando len(A) != len(B) e, in questo esempio, len(A) > len(B). Per evitare ciò, è possibile aggiungere un'altra dichiarazione.

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

Una cosa di più, mi benchmark mia soluzione con timeit.repeat, alle stesse condizioni utilizzate da Aaron Hall nel suo post. Come sospettato, i risultati sono deludenti. Il mio metodo è l'ultimo. set(x) == set(y) lo è.

>>> 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

Come accennato nei commenti sopra, il caso generale è un dolore. È abbastanza facile se tutti gli oggetti sono lavabili o tutti gli oggetti sono ordinabili. Tuttavia, di recente ho dovuto provare a risolvere il caso generale. Ecco la mia soluzione. Mi sono reso conto dopo aver postato che questo è un duplicato di una soluzione sopra che ho perso al primo passaggio. Ad ogni modo, se usi slice anziché list.remove() puoi confrontare sequenze immutabili.

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