CODEWITHSUNDEEP
python
Reza Afra
Reza Afra

Reputation: 31

Pythonic Closest Pair Naive

I am trying to write the brute-force version of closest pair algorithm without using nested for loops. This is the code I have written but the code gives me 0.0 because I am calculating the distance of points with themselves. How can I change the code to give me the correct minimum distance?

import math

x = [4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2]  
y = [4, -2, -4,  3, 3,  0, 1, -1, -1, 2,  4] 

def _ClosestPair(x,y):  
    Px = sorted(list(zip(x,y)), key = lambda elem: elem[0])  
    return ClosestPairNaive(Px)

def ClosestPairNaive(points):
    dis = lambda p, q: math.sqrt((p[0]-q[0])**2 +  (p[1] - q[1])**2)
    return  min([dis(p,q) for p in points[:len(points)-1] for q in points[1:]])

print(_ClosestPair(x, y))

Upvotes: 0

Views: 81

Answers (2)

0x Tps
0x Tps

Reputation: 165

Single statement

return  min([[dis(p,q),p,q] for p in points[:len(points)-1] for q in points[1:] if p!=q])

Upvotes: 0

juanpa.arrivillaga
juanpa.arrivillaga

Reputation: 96172

The idiomatic way too loop over every positionally unique pair in a list is to start from i + 1 in the inner loop:

In [4]: data = 'abc'

In [5]: [(data[i], data[j]) for i in range(len(data)) for j in range(i+1, len(data))]
Out[5]: [('a', 'b'), ('a', 'c'), ('b', 'c')]

In [6]: data = 'abcd'

In [7]: [(data[i], data[j]) for i in range(len(data)) for j in range(i+1, len(data))]
Out[7]: [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

It's a simple and effective algorithm when working with sequence types.

Also note, math has a handy hypot function, which is simply the euclidean norm. So you could implement this simply as:

In [8]: ps = list(zip(
    ...:     [4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2],
    ...:     [4, -2, -4,  3, 3,  0, 1, -1, -1, 2,  4]
    ...: ))

In [9]: import math
    ...: def dis(p1, p2):
    ...:     (x0, y0), (x1, y1) = p1, p2
    ...:     return math.hypot(x1 - x0, y1 - y0)
    ...:

In [10]: min(dis(ps[i], ps[j]) for i in range(len(ps)) for j in range(i + 1, len(ps)))
Out[10]: 1.4142135623730951

Note, assigning the result of a lambda expression to a name is explicitely against PEP8. For that matter, you should be using snake_case instead of CapitalCase for your function names.

Upvotes: 1

Related Questions