У меня есть список пар:
[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]
и я хочу удалить любые дубликаты, где
[a,b] == [b,a]
Итак, мы закончили с помощью
[0, 1], [0, 4], [1, 4]
Я могу выполнить внутренний и внешний цикл для обратной пары и добавить к списку, если это не так, но я уверен, что есть более Pythonic способ достижения тех же результатов.
Если вам нужно сохранить порядок элементов в списке, вы можете использовать функцию sorted и установить понимание с map следующим образом:
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)}
или просто без map следующим образом:
data = {tuple(sorted(item)) for item in lst}
Другой способ - использовать frozenset, как показано здесь, однако обратите внимание, что это работает только в том случае, если у вас есть отдельные элементы в вашем списке. Поскольку set, frozenset всегда содержит уникальные значения. Таким образом, вы получите уникальную ценность в своей подсписке (потеряете данные), которая может быть не такой, какой вы хотите.
Чтобы вывести список, вы всегда можете использовать list(map(list, result)), где result является набором кортежей только в Python-3.0 или более поздней версии.
Если вы хотите удалить только парные пары и не хотите использовать внешние библиотеки, вы можете использовать простую функцию генератора (на основе 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]]
Функция генератора может быть довольно быстрым способом решить эту проблему, потому что набор запросов действительно дешев. Этот подход также сохраняет порядок вашего первоначального списка и удаляет обратные дубликаты только быстрее, чем большинство альтернатив!
Если вы не возражаете использовать внешнюю библиотеку и хотите удалить все дубликаты (обратные и идентичные), альтернатива: 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]]
Это проверяет, имеет ли какой-либо элемент то же содержимое в суровом порядке (таким образом, key=set) как другое. В этом случае это работает так, как ожидалось, но также удаляет дубликат [a, b], а не только [b, a] вхождения. Вы также можете использовать key=sorted (как и другие ответы). unique_everseen, как это, имеет плохую алгоритмическую сложность, потому что результат функции key не хешируется, и, следовательно, быстрый поиск заменяется медленным поиском. Чтобы ускорить это, вам нужно сделать ключи хешируемыми, например, переведя их в отсортированные кортежи (как подсказывают некоторые другие ответы):
>>> from iteration_utilities import chained
>>> list(unique_everseen(a, key=chained(sorted, tuple)))
[[0, 1], [0, 4], [1, 4]]
chained - не что иное, как более быстрая альтернатива lambda x: tuple(sorted(x)).
EDIT: Как уже упоминалось @jpmc26, вместо обычных наборов можно использовать frozenset:
>>> list(unique_everseen(a, key=frozenset))
[[0, 1], [0, 4], [1, 4]]
Чтобы получить представление об эффективности, я сделал несколько сравнений timeit для разных предложений:
>>> 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
Длинный список со многими дубликатами:
>>> 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
И с меньшим количеством дубликатов:
>>> 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
Таким образом, варианты с remove_reversed_duplicates, unique_everseen (key=frozenset) и set(map(frozenset, a)) кажутся, безусловно, самыми быстрыми решениями. Какой из них зависит от длины ввода и количества дубликатов.
set(map(frozenset, lst))
Если пары логически неупорядочены, они более естественно выражаются как множества. Было бы лучше иметь их как набор, прежде чем вы доберетесь до этого момента, но можете их преобразовать следующим образом:
lst = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
lst_as_sets = map(frozenset, lst)
И тогда естественным способом устранения дубликатов в итерабельном является преобразование его в set:
deduped = set(lst_as_sets)
(Это основная причина, по которой я выбрал frozenset на первом шаге. Mutable set не хешируется, поэтому их нельзя добавить в set.)
Или вы можете сделать это в одной строке, как в разделе TL; DR.
Я думаю, что это намного проще, интуитивно понятнее и более точно соответствует тому, как вы думаете о данных, чем суете с сортировкой и кортежами.
Если по какой-то причине вам действительно нужен list of list в качестве конечного результата, преобразование обратно тривиально:
result_list = list(map(list, deduped))
Но скорее логично оставить все как set как можно дольше. Я могу только подумать об одной причине, которая вам может понадобиться, и о совместимости с существующими кодами/библиотеками.
Вы можете отсортировать каждую пару, преобразовать список пар в набор кортежей и обратно:
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]]
Этапы могут быть проще понять, чем длинные однострочные:
>>> 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]]
Вы можете использовать встроенную функцию filter.
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]]
В качестве дополнения я бы привязал вас к Модуль Python itertools, который описывает функцию unique_everseen, которая делает в основном то же самое, что и выше, но в ленивой, основанной на генераторе, эффективной для памяти версии. Может быть лучше любого из наших решений, если вы работаете с большими массивами. Вот как его использовать:
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]]
Я не делал никаких показателей, чтобы узнать, кто быстрее. Однако эффективность памяти и сложность O выглядят лучше в этой версии.
Встроенная функция sorted может быть передана в unique_everseen для заказа элементов во внутренних векторах. Вместо этого я прохожу lambda x: (min(x), max(x)). Поскольку я знаю размер вектора, который равен ровно 2, я могу продолжать это.
Чтобы использовать sorted, мне нужно передать lambda x: tuple(sorted(x)), который добавляет дополнительные служебные данные. Не драматично, но все же.
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
Сроки, выполняемые в Python 3, который добавляет globals kwarg к timeit.timeit.
Простое и неутешительное решение:
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
Сначала отсортируйте каждый список, а затем используйте ключи словарей, чтобы получить уникальный набор элементов и их понимание списка.
Почему кортежи?
Замена списков с помощью кортежей необходимо, чтобы избежать "немой" ошибки при прохождении функции 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)) ]
Использование OrderedDict даже сохраняет порядок списка.
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)) ]
Приведенный выше код приведет к желаемому списку
[[0, 1], [0, 4], [1, 4]]
Если порядок пар и пар элементов имеет значение, создание нового списка путем тестирования для членства может быть здесь.
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)
В противном случае я бы пошел с ответом Styvane.
Кстати, вышеупомянутое решение не будет работать для случаев, когда у вас есть соответствующие пары. Например, [0,0] не будет добавлен в список. Для этого вам нужно добавить дополнительную проверку:
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)
Однако это решение не будет принимать пустые "пары" (например, []). Для этого вам понадобится еще одна настройка:
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)
Бит and not pair in no_dups требуется для предотвращения добавления [0,0] или [] в no_dups дважды.
Ну, я "проверяю обратную пару и добавляю к списку, если это не так", как вы сказали, что можете сделать, но я использую один цикл.
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
Преимущество над существующими ответами - это ИМО, более читаемое. Здесь нет глубоких знаний о стандартной библиотеке. И не отслеживать ничего сложного. Единственная концепция, которая может быть незнакомой для новичков, которая [::-1] возвращает пару.
Производительность O (n ** 2), однако, не следует использовать, если производительность является проблемой и/или списки являются большими.