python - 无顺序且允许重复的可散列数据结构

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 中实现它？

标签： pythonpython-3.xsettupleshashable

Answer 1

您可以对元组进行排序并用于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)]
}