Python:迭代一个集合，这样我们就不会多次比较相同的对象？

Question

所以我正在写一个游戏。这是碰撞检测的工作原理；有一个不可见的网格，对象(或者更确切地说，它们的引用)根据它们所在的位置从单元格中添加和删除。碰撞比较仅在同一单元格中的对象之间进行。

引用存储在 Python set 中这是每个细胞所拥有的。它必须是一个集合。当检测到碰撞时，它存储在 Collision 中。具有三个属性的对象；碰撞的两个物体和碰撞发生的时间。考虑到所有碰撞后，它们会按时间排序，然后进行处理。

这是单个单元格用来检查碰撞的循环；

#grid.collisions is a list of recorded collisions, and self.objects is the set
#of objects currently in this cell.

for i in self.objects:
    for j in self.objects:
        if id(i) != id(j) and pygame.sprite.collide_rect(i, j):
            grid.collisions.append(Collision(i, j))

问题是，这会将相同的两个对象进行两次比较；如果我们有一套{1, 2, 3, 4} ，我们会比较 (1, 2) 和 (2, 1) .不仅如此，这些重复比较还被添加到总冲突列表中，从而破坏了整个系统!

我知道我不能索引集，这意味着我不能做类似 for j in range(i, len(self.objects)) 的事情其中 i和 j都是整数。 我如何绕过这个限制以确保同一组中的两个对象不会被比较两次？我不能删除这些组中的对象；只有当对象离开网格单元时，它们才会被删除。

由于这些碰撞在每一帧都被处理，我宁愿避免创建新对象(实际代码不会像示例那样创建新的 Collisions，我只是为了便于阅读而对其进行了简化)。我可以只删除重复的比较，但将每个碰撞与其他碰撞进行比较会产生大量开销。

Answer 1

如果您的目标只是比较该集合的所有独特组合，您可以使用 itertools.combinations

from itertools import combinations

for i, j in combinations(self.objects, 2):
    if pygame.sprite.collide_rect(i, j):
        grid.collisions.append(Collision(i, j))

例子:

aSet = set([1,2,3,4])
list(combinations(aSet, 2))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

组合 生成的生成器与管理多个索引和临时列表相比非常高效