python-3.x 无顺序且允许重复的可哈希数据结构

xuo3flqw  于 2023-03-20  发布在  Python
关注(0)|答案(4)|浏览(140)

我有元组列表/列表(-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)Map到相同的东西,我想到了set这样的东西,但它会删除元组中可能存在的任何重复项。
在生成一个新的元组(比如(-1,-1,2))时,我想执行一个检查,如下所示

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

为此,我需要数据结构是可散列的,以便进行O(1)查找。2有什么想法我将如何在Python中实现这一点吗?

whlutmcx

whlutmcx1#

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

klh5stk12#

你可以使用collections.Counter来有效地获取列表中每个元组的签名,将Counter对象的项Map到frozensets,这样签名就可以哈希了,将它们放入一个集合中去重,然后使用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)]
hfsqlsce

hfsqlsce3#

您可以使用set来避免添加Map到同一事物的元素。

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
3hvapo4f

3hvapo4f4#

multisetpackage中的FrozenMultiset做你想要的事情。
抽象地说,多重集是无序的,并且“允许”重复。幸运的是,多重集的一些实现是不可散列的,但FrozenMultiset不是。

相关问题