python - Hashable data structure with no order and allowed duplicates

Question

I have list of tuples/lists (-1, 0, 1) (-1, 1, 0) (-1, 2, -1) (-1, -1, 2) (0, 1, -1)

I need them to be : (-1, 1, 0) (-1, 2, -1)

I want (-1, 0, 1) and (-1, 1, 0) map to the same thing. I thought of something like set but that would remove any duplicates I might have in the tuple.

While generating a new tuple say (-1,-1,2) I want to perform a check like

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

for this I need the data structure to be hashable for O(1) lookup. Any ideas how I would implement this in Python?

Answer 1

You could sort the tuples and use set to check for duplicates as tuples are hashable

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

Output

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

Can use 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)

Output:

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