Python最近对奈

Question

我正在尝试编写最接近对算法的暴力版本，而不使用嵌套for循环。这是我写的代码，但是代码给了我0.0，因为我在计算点与它们之间的距离。如何更改代码以获得正确的最小距离？你知道吗

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))

Answer 1

在列表中的每个位置唯一对上循环的惯用方法是从内部循环中的i + 1开始：

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')]

在处理序列类型时，它是一个简单而有效的算法。你知道吗

还要注意，math有一个方便的hypot函数，它只是欧几里德范数。因此，您可以简单地将其实现为：

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

请注意，将lambda表达式的结果指定给名称是针对PEP8的。因此，应该使用snake_case而不是CapitalCase作为函数名。你知道吗

Answer 2

单一语句

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