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

У меня есть список кортежей/списков (-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?


python-3.x python set tuples hashable
person Ajinkya Gawali    schedule 20.03.2019    source источник
comment
Вы можете отсортировать элементы кортежа, если я понимаю, о чем вы спрашиваете.   -  person Scott Hunter    schedule 20.03.2019
comment
Почему (-1, 0, 1) и (-1, 1, 0) одинаковы, ведь они имеют одинаковые значения, но не упорядочены?   -  person Martijn Pieters    schedule 20.03.2019
comment
Это, вероятно, невозможно сделать в O(1), потому что преобразование кортежа и его сравнение всегда не менее O(n) (средний случай), где n — количество элементов в кортеже.   -  person MSeifert    schedule 20.03.2019
comment
@MSeifert хорошо, но это зависит от того, что такое N, верно? Если размер кортежей не меняется, то это не повлияет на сложность. IOW, это по-прежнему будет линейно масштабироваться по количеству кортежей. У вас просто более высокий постоянный коэффициент из-за дорогостоящей хеш-функции.   -  person juanpa.arrivillaga    schedule 20.03.2019
comment
@juanpa.arrivillaga Да, однако это только подразумевается в вопросе. Было бы неплохо, если бы это прояснили. :)   -  person MSeifert    schedule 20.03.2019

Ответы (3)


arrow_upward
0
arrow_downward

Вы можете отсортировать кортежи и использовать 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)]
}
person mad_    schedule 20.03.2019
comment
В заголовке вопроса говорится, что нет порядка, но он соответствует функциональным требованиям. - person MSeifert; 20.03.2019
comment
Ааа не читал вопрос. O (1) трудно достичь, так как есть шансы на большее столкновение. - person mad_; 20.03.2019

arrow_upward
0
arrow_downward

Вы можете использовать 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)]
person blhsing    schedule 20.03.2019
comment
Результат неверный, ожидалось (-1, 1, 0) (-1, 2, -1). - person MSeifert; 20.03.2019
comment
Порядок элементов в кортеже не имеет значения, как указано в ОП, и именно поэтому кортежи с разным порядком в первую очередь считаются дубликатами. - person blhsing; 20.03.2019
comment
Ах, я думал, что это просто требование для сравнения, а не для результата. Хотя немного непонятно - person MSeifert; 20.03.2019
comment
Что ж, если OP хочет сохранить в результате первый кортеж каждой уникальной комбинации элементов, ожидаемым результатом будет (-1, 0, 1), (-1, 2, -1). Для меня тот факт, что OP ожидает, что (-1, 1, 0) будет в выводе, означает, что порядок на самом деле не имеет значения. Но да, здесь было бы неплохо получить некоторые разъяснения от ОП. - person blhsing; 20.03.2019

arrow_upward
0
arrow_downward

Вы можете использовать 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
person Hugo Delahaye    schedule 20.03.2019
comment
Это определенно не O(1), когда у вас есть вложенные циклы. - person MSeifert; 20.03.2019
comment
Например, это будет неправильно рассматривать (-1, -1, 2) как дубликат (-1, 2, 2). - person blhsing; 20.03.2019