如何生成给定坐标曼哈顿距离R范围内的所有坐标？Python实现求助

核心思路 #

直接利用曼哈顿距离的定义 |x| + |y| ≤ r，对每个x值计算出y的有效范围，完全避免遍历无效坐标，这是最优解法，没有多余计算。

实现代码 #

列表版本（一次性生成所有坐标）

def generate_manhattan_coords(r):
    coords = []
    for x in range(-r, r + 1):
        max_y = r - abs(x)
        for y in range(-max_y, max_y + 1):
            coords.append((x, y))
    return coords

生成器版本（节省内存，按需获取）

如果r值很大，坐标总量会非常多，用生成器可以避免一次性占用大量内存：

def generate_manhattan_coords_gen(r):
    for x in range(-r, r + 1):
        max_y = r - abs(x)
        for y in range(-max_y, max_y + 1):
            yield (x, y)

效率对比 #

你之前的方法是遍历x、y均从-r到r的所有组合再筛选，会遍历(2r+1)^2个点，但其中只有(r+1)(2r+1)个有效点（曼哈顿半径内点的总数公式），无效遍历占比接近一半。而上面的方法只生成符合条件的坐标，完全没有多余计算，效率达到理想情况的100%。

内容的提问来源于stack exchange，提问作者Simon Knight