Хасовая структура данных без порядка и разрешенных дубликатов

Question

У меня есть список кортежей / списков (-1, 0, 1) (-1, 1, 0) (-1, 2, -1) (-1, -1, 2) (0, 1, -1)

Мне нужно, чтобы они были: (-1, 1, 0) (-1, 2, -1)

Я хочу (-1, 0, 1) и (-1, 1, 0) сопоставить с тем же.Я думал о чем-то вроде set, но это удаляло бы любые дубликаты, которые я мог бы иметь в кортеже.

При создании нового кортежа, скажем (-1, -1,2), я хочу выполнить проверку наподобие

if (-1,-1,2) in seen:
   pass
else:
     insert(seen, (-1,-1,2))

, для этого мне нужно, чтобы структура данных была хешируемой для O (1) поиск.Любые идеи, как я бы реализовать это в Python?

Answer 1

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

l = [(-1, 0, 1), (-1, 1, 0), (-1, 2, -1), (-1, -1, 2), (0, 1, -1)]

new_l = []

for i in l:
    if set(i) not in [set(j) for j in new_l]:
        new_l += [i]

print new_l

Возвращает [(-1, 0, 1), (-1, 2, -1)]

Редактировать

Это неправильно помечает некоторые кортежи как дубликаты. Это должно работать:

l = [(-1, 0, 1), (-1, 1, 0), (-1, 2, -1), (-1, -1, 2), (0, 1, -1)]

new_l = list(set([tuple(sorted(i)) for i in l]))

print new_l

Answer 2

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

from collections import Counter
l = [(-1, 0, 1), (-1, 1, 0), (-1, 2, -1), (-1, -1, 2), (0, 1, -1)]
[tuple(Counter(dict(i)).elements()) for i in {frozenset(Counter(t).items()) for t in l}]

Возвращает:

[(0, -1, 1), (-1, -1, 2)]

Answer 3

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

a=[(-1, 0, 1) ,(-1, 1, 0), (-1, 2, -1) ,(-1, -1, 2), (0, 1, -1)]
my_set=set()
res=[]
for original_value, sorted_value in zip(a,map(sorted,a)):
    if tuple(sorted_value) not in my_set:
        res.append(original_value)
        my_set.add(tuple(sorted_value))

Выход

[(-1, 0, 1), (-1, 2, -1)]

Можно использовать defaultdict

from collections import defaultdict
d=defaultdict(list)
a=[(-1, 0, 1) ,(-1, 1, 0), (-1, 2, -1) ,(-1, -1, 2), (0, 1, -1)]

res=[]
for original_value, sorted_value in zip(a,map(sorted,a)):
    d[tuple(sorted_value)].append(original_value)

Выход:

{
(-1, -1, 2): [(-1, 2, -1), (-1, -1, 2)], 
(-1, 0, 1): [(-1, 0, 1), (-1, 1, 0), (0, 1, -1)]
}