26

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, jused 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.

Ankur Ankan
  • 2,953
  • 2
  • 23
  • 38

7 Answers7

42

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.

Martijn
  • 13,225
  • 3
  • 48
  • 58
Kiv
  • 31,940
  • 6
  • 44
  • 59
  • 1
    Note that the 'key' argument to min is only accepted since 2.5 – David Hanak Jan 29 '09 at 21:18
  • I would have used zip(nums, nums) instead of the listcomp, but otherwise that would have been my solution. – John Fouhy Jan 29 '09 at 21:48
  • 1
    Actually, zip(nums, nums) results in [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)], which is not correct. – Kiv Jan 29 '09 at 22:06
  • 1
    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 Feb 04 '09 at 17:32
  • For those wondering about the single underscore in the posted code: [What is the purpose of the single underscore “_” variable in Python?](http://stackoverflow.com/q/5893163/1025391) – moooeeeep Jan 08 '16 at 07:44
10

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)
Kenan Banks
  • 207,056
  • 34
  • 155
  • 173
3

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
  • 38,188
  • 14
  • 54
  • 77
3

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, etc.

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
  • 109,094
  • 6
  • 73
  • 101
1

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
  • 5,705
  • 1
  • 32
  • 30
  • BTW, Does not do what the question asks. Yes, it is the solution to the simple example in the question, but it does not say how to apply some function to pairs of numbers. (Or perhaps the question was improved after this answer was posted.) – ToolmakerSteve Dec 08 '13 at 01:44
1

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)
tzot
  • 92,761
  • 29
  • 141
  • 204
  • 1
    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 Jun 19 '09 at 23:45
  • @liori: the OP does not seem to want euclidean distances. Thanks for your comment, anyway, since it reminded me of the question. – tzot Jun 20 '09 at 08:03
0
>>> 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)
waitingkuo
  • 89,478
  • 28
  • 112
  • 118
Chandrakant Silver
  • 1
  • 1