Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

python

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 some 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 appended 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 this clearly picks up each collision twice, which lead to some strange behavior when trying to resolve them. So what is the pythonic solution here?

like image 973
Bogdanovist Avatar asked May 17 '13 07:05

Bogdanovist


People also ask

How do you compare individual items in a list in Python?

Python set() method and == operator to compare two lists Further, the == operator is used for comparison of the data items of the list in an element-wise fashion.

How do you compare each element in an array in Python?

To compare each element of a NumPy array arr against the scalar x using any of the greater (>), greater equal (>=), smaller (<), smaller equal (<=), or equal (==) operators, use the broadcasting feature with the array as one operand and the scalar as another operand.


1 Answers

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 here to generate all possible combinations:

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 still write this using index-based item access, equivalent to what you are used to, using nested for loops:

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

Of course this may not look as nice and pythonic but sometimes this is still the easiest and most comprehensible solution, so you should not shy away from solving problems like that.

like image 124
poke Avatar answered Oct 05 '22 12:10

poke