Bogdanovist Bogdanovist - 1 month ago 6
Python Question

How to compare each item in a list with the rest, only once?

Say I have an array/list of things I want to compare. In languages I am more familiar with, I would do something like

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


This ensures we only compare each pair once. For context, I am doing collision detection on a bunch of objects contained in the list. For each collision detected, a small 'collision' object describing the collision is append to a list, which another routine then loops through resolving each collision (depending on the nature of the two colliding objects). Obviously, I only want to report each collision once.

Now, what is the pythonic way of doing this, since python favors using iterators rather than looping over indices?

I had the following (buggy) code

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


but clearly this picks up each collision twice, which lead to some strange behavior when trying to resolve them. So what is the pythonic solution here?

Answer

Of course this will generate each pair twice as each for loop will go through every item of the list. You could use some itertools magic:

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

itertools.combinations will pair each element with each other element in the iterable, but only once.

You could also write this as for i in range(..) loops, equivalent to your other code there:

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