views:

12137

answers:

8

Given [1,2,3,4,5], how can i do something like 1/1, 1/2, 1/3,1/4,1/5, ...., 3/1,3/2,3/3,3/4,3/5,.... 5/1,5/2,5/3,5/4,5/5

I would like to store all the results, find the minimum, and return the two numbers used to find the minimum. So in the case i've described above i would like to return (1,5).

So basically I would like to do something like

for each element i in the list map some function across all elements in the list, taking i and j as parameters store the result in a master list, find the minimum value in the master list, and return the arguments i, j used to calculate this minimum value.

In my real problem i have a list objects/coordinates, and the function I am using takes two coordinates and calculates the euclidean distance. I'm trying to find minimum euclidean distance between any two points but I don't need a fancy algorithm.

+1  A: 

Try this resource

Cade Roux
Interesting, but perhaps overkill here.
Kiv
+14  A: 

You can do this using list comprehensions and min() (Python 3.0 code):

>>> nums = [1,2,3,4,5]
>>> [(x,y) for x in nums for y in nums]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]
>>> min(_, key=lambda pair: pair[0]/pair[1])
(1, 5)

Note that to run this on Python 2.5 you'll need to either make one of the arguments a float, or do from __future__ import division so that 1/5 correctly equals 0.2 instead of 0.

Kiv
Note that the 'key' argument to min is only accepted since 2.5
David Hanak
I would have used zip(nums, nums) instead of the listcomp, but otherwise that would have been my solution.
John Fouhy
Actually, zip(nums, nums) results in [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)], which is not correct.
Kiv
For a better use of memory, instead of a list, you can use a generator:nums = [1, 2, 3, 4, 5]pairs = ((x, y) for x in nums for y in nums)m = min(pairs, key=lambda pair: pair[0] / pair[1])Thus, each pair is generated sequentially, which is more memory-efficient than keeping a list of pairs.
Leonel
Yes, that is essentially Triptych's answer and it is more memory efficient. I deliberately chose the list here so that it would print out intermediate output and demonstrate what's going on.
Kiv
A: 

Some readable python:

def JoeCalimar(l):
    masterList = []
    for i in l:
        for j in l:
            masterList.append(1.*i/j)
    pos = masterList.index(min(masterList))
    a = pos/len(masterList)
    b = pos%len(masterList)
    return (l[a],l[b])

Let me know if something is not clear.

Andrea Ambu
+6  A: 

If I'm correct in thinking that you want to find the minimum value of a function for all possible pairs of 2 elements from a list...

l = [1,2,3,4,5]

def f(i,j):
   return i+j 

# Prints min value of f(i,j) along with i and j
print min( (f(i,j),i,j) for i in l for j in l)
Triptych
You beat me by 7 seconds ;-)
oefe
hahaha sorry. Believe me I've been on the other end of that race condition.
Triptych
Lists named "l" freak me out a little bit. Good solution though :)
Kiv
Yeah, I always call my generic lists 'lst'.
John Fouhy
I'd add a [1:] at the end: print min( (1.*i/j,i,j) for i in l for j in l)[1:]
Andrea Ambu
Thought about it, but it felt much less readable to me @Andrea
Triptych
@Triptych: the 1.*i/j or the [1:] ?!?
Andrea Ambu
@Andreas, the [1:]. I abstracted out the division to make it clear that any function could be there.
Triptych
+1  A: 

Doing it the mathy way...

nums = [1, 2, 3, 4, 5]
min_combo = (min(nums), max(nums))

Unless, of course, you have negatives in there. In that case, this won't work because you actually want the min and max absolute values - the numerator should be close to zero, and the denominator far from it, in either direction. And double negatives would break it.

Nikhil Chelliah
+1  A: 

If you don't mind importing the numpy package, it has a lot of convenient functionality built in. It's likely to be much more efficient to use their data structures than lists of lists and the like.

from __future__ import division

import numpy

data = numpy.asarray([1,2,3,4,5])
dists = data.reshape((1,5)) / data.reshape((5,1))

print dists

which = dists.argmin()
(r,c) = (which // 5, which % 5) # assumes C ordering

# pick whichever is most appropriate for you...
minval = dists[r,c]
minval = dists.min()
minval = dists.ravel()[which]
Mr Fooz
+1  A: 

If working with Python ≥2.6 (including 3.x), you can:

from __future__ import division
import operator, itertools

def getmin(alist):
    return min(
        (operator.div(*pair), pair)
        for pair in itertools.product(alist, repeat=2)
    )[1]

getmin([1, 2, 3, 4, 5])

EDIT: Now that I think of it and if I remember my mathematics correctly, this should also give the answer assuming that all numbers are non-negative:

def getmin(alist):
    return min(alist), max(alist)
ΤΖΩΤΖΙΟΥ
If the OP wants to calculate euclidean distance, there's itertools.combinations generator which will yield only unique pairs of different values from input.
liori
@liori: the OP does not seem to want euclidean distances. Thanks for your comment, anyway, since it reminded me of the question.
ΤΖΩΤΖΙΟΥ
A: 

>>> nums = [1, 2, 3, 4, 5]

>>> min(map((lambda t: ((float(t[0])/t[1]), t)), ((x, y) for x in nums for y in nums)))[1]

(1, 5)

Chandrakant Silver