如何连续生成二维列表，直到满足特定规范

Question

我编写了以下Python程序：

该程序生成30x30二维列表，并在网格周围随机放置10个标记。我想修改此程序，以便在放置标记时连续生成30x30 2D，并且仅当每个标记之间有一定的间距（例如至少相距5米）时停止。我知道我必须使用毕达哥拉斯定理来实现这一点，但不知道如何在代码中实现它

import random
listSize = 30
marks = 10
grid = []
for i in range(listSize): 
    grid.append([0] * listSize)
for i in range(marks):
    x = random.randint(0, listSize - 1)
    y = random.randint(0, listSize - 1)
    grid[x][y] = 1 
for row in grid:
    print(row)

Answer 1

与其在网格中存储标记，不如创建一个加法列表来存储每个标记的x、y位置，然后循环检查每对标记是否满足条件。比如说：

import math

points = [(0,0), (5,10), (100,200)]
for n, point_n in enumerate(points):
    for point_m in points[n+1:]:
        if math.dist(point_n, point_m) < 5:
            print('distance less than 5!')

注意math.dist仅在Python3.8及更高版本中可用，您必须自己在更低版本中编写距离函数

Answer 2

这里有一个有点天真的命中或未命中的方法：

from math import sqrt
from random import randint
from itertools import combinations

def dist(p,q):
    return sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)

def rand_points(n,k):
    """picks n random points with coordinates in range(k)"""
    #assumes that this is feasible!
    choices = set()
    for _ in range(n):
        while True:
            p = (randint(0,k-1),randint(0,k-1))
            if p not in choices:
                choices.add(p)
                break
    return list(choices)

def check_points(points,min_dist):
    """checks if each point is at least min_dist away from other points"""
    return all(dist(p,q) >= min_dist for p,q in combinations(points,2))

def find_points(grid_size,num_points,min_dist,max_trials = 1000):
    for trial in range(max_trials):
        points = rand_points(num_points,grid_size)
        if check_points(points,min_dist):
            return points

例如：

>>> find_points(30,10,5)
[(26, 9), (6, 0), (29, 23), (17, 13), (12, 19), (2, 22), (2, 28), (3, 9), (1, 16), (18, 5)]

当然，将这样的点列表加载到网格中很容易：

def grid_from_points(grid_size,points):
    grid = [[0]*grid_size for _ in range(grid_size)]
    for p,q in points:
        grid[p][q] = 1
    return grid
        points = rand_points(num_points,grid_size)
        if check_points(points,min_dist):
            return points