如何将列表中的每一项与其他项进行比较，仅进行一次？

Question

假设我有一个要比较的数组/列表。在我比较熟悉的语言中，我会做一些

for (int i = 0, i < mylist.size(); i++)
    for (int j = i + 1, j < mylist.size(); j++)
        compare(mylist[i], mylist[j])

这确保我们只对每一对进行一次比较。对于某些上下文，我正在对列表中包含的一组对象执行碰撞检测。对于检测到的每个碰撞，一个描述碰撞的小“碰撞”对象被附加到一个列表中，然后另一个例程循环解决每个碰撞（取决于两个碰撞对象的性质）。很明显，每次碰撞我只想报告一次。

既然Python喜欢使用迭代器而不是循环索引，那么Python的这种方式是什么呢？

我有以下代码：

for this in mylist:
    for that in mylist:
        compare(this, that)

但很明显，每次碰撞都会出现两次，这在试图解决碰撞时会导致一些奇怪的行为。那么什么是Python的解决方案呢？

Answer 1

我认为在外部循环上使用enumerate并使用索引在内部循环上对列表进行切片是非常愚蠢的：

for index, this in enumerate(mylist):
    for that in mylist[index+1:]:
        compare(this, that)

Answer 2

当然，这将生成每一对，因为每个for循环将遍历列表中的每个项。

您可以在这里使用一些itertools魔法来生成所有可能的组合：

import itertools
for a, b in itertools.combinations(mylist, 2):
    compare(a, b)

^{}将iterable中的每个元素与其他元素配对，但只配对一次。

---

您仍然可以使用基于索引的项访问（相当于您习惯的访问）来编写它，使用嵌套的for循环：

for i in range(len(mylist)):
    for j in range(i + 1, len(mylist)):
        compare(mylist[i], mylist[j])

当然，这可能看起来不太好，但有时这仍然是最简单和最容易理解的解决方案，所以你不应该回避解决这样的问题。

Answer 3

使用itertools.combinations(mylist, 2)

mylist = range(5)
for x,y in itertools.combinations(mylist, 2):
    print x,y

0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4