Определите, имеют ли 2 списка одинаковые элементы, независимо от порядка? [дубликат]

этот вопрос уже есть ответ здесь:

извините за простой вопрос, но мне трудно найти ответ.

когда я сравниваю 2 списка, я хочу знать, если они "равны" в том, что они имеют то же самое содержание, но в другом порядке.

Ex:

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

Я хочу x == y оценка для True.

4 80
python list python-2.x equality

4 ответа:

вы можете просто проверить, равны ли мультинаборы с элементами x и y:

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

для этого требуется элементы, которые должны быть hashable; во время выполнения будет в O(n), где n - размер списков.

если элементы также уникальны, вы также можете конвертировать в наборы (то же асимптотическое время выполнения, может быть немного быстрее на практике):

set(x) == set(y)

если элементы не хэшируются, но сортируются, другая альтернатива (время выполнения в O(n log n)) это

sorted(x) == sorted(y)

если элементы не hashable, ни сортировки, можно использовать следующую вспомогательную функцию. Обратите внимание, что это будет довольно медленно (O(n²)) и вообще не используется за пределами эзотерического случая неразборчивых и несортируемых элементов.

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
114

определить, если 2 списка имеют одинаковые элементы, независимо от порядка?

вывод из вашего примера:

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

что элементы списков не будут повторяться (они уникальны), а также хэшироваться (какие строки и другие определенные неизменяемые объекты python),самый прямой и вычислительно эффективный ответ использует встроенные наборы Python, (которые семантически похожи на математические наборы, которые вы можете узнали об этом еще в школе). 

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

в случае, если элементы hashable, но не уникальный,collections.Counter также работает семантически как мультимножество, но это гораздо медленнее:

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

предпочитаю использовать sorted:

sorted(x) == sorted(y)

если элементы упорядочиваются. Это будет учитывать не уникальные или не хешируемые обстоятельства, но это может быть намного медленнее, чем использование наборов.

эмпирическая Эксперимент

эмпирический эксперимент заключает, что следует предпочесть set, потом sorted. Только выбрать для Counter если вам нужны другие вещи, такие как подсчеты или дальнейшее использование в качестве мультинабора.

настройки:

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)

и тестирования:

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

Итак, мы видим, что сравнение наборов является самым быстрым решением, а сравнение отсортированных списков-вторым по скорости.

12

это, кажется, работает, хотя, возможно, громоздко для больших списков.

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

однако, если каждый список должны содержат в себе все элементы других, то приведенный выше код является проблематичным. 

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

проблема возникает, когда len(A) != len(B) и, в этом примере len(A) > len(B). Чтобы избежать этого, можно добавить еще одно заявление.

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

еще одна вещь, я сравнил свое решение с timeit.повторяю, при тех же условиях, которые использовал Аарон Холл в своей должность. Как и предполагалось, результаты неутешительны. Мой метод-последний. set(x) == set(y) это.

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

Как упоминалось в комментариях выше, общий случай-это боль. Это довольно легко, если все элементы хэшируются или все элементы сортируются. Однако мне недавно пришлось попробовать решить общий случай. Вот мое решение. Я понял после публикации, что это дубликат решения выше, которое я пропустил на первом проходе. Во всяком случае, если вы используете срезы, а не список.удалить() вы можете сравнить неизменяемые последовательности.

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
0