Блог

Я искал решение проблемы с ближайшей парой в Python, но все решения полностью отличались от моих.

Вот код, который находит ближайшую пару точек в 2D-измерении.

 def closest_pair_two_axes(xarr, yarr):
    pairs = []
    # doesn't really depend if xarr or yarr because the lengths are the same
    for i in range(len(xarr)):
        pairs.append([xarr[i], yarr[i]])

    # Finds the difference between each point
    dist_arr = []
    for i in range(1, len(pairs)-1):
        for j in range(i, len(pairs)):
            diff_x = pairs[j][0] - pairs[j - i][0]
            diff_y = pairs[j][1] - pairs[j - i][1]

            diff = (diff_x ** 2   diff_y ** 2) ** 0.5
            dist_arr.append(round(diff, 2))

    index = dist_arr.index(min(dist_arr))
    closest_distance = dist_arr[index]

    return closest_distance
 

xarr и yarr являются просто именами массивов для координат x и y. В функции я объединяю оба массива в словарь, содержащий наборы координат. После этого я перебираю все возможные комбинации координат и нахожу расстояние между каждым из них. В конце концов, я нахожу минимальное расстояние, отслеживаю его до пары, к которой он принадлежит, а затем возвращаю его пользователю.

Этот код работает, но я не уверен, правильно ли он работает и действительно ли результат является ближайшей парой. Правильный ли код?

РЕДАКТИРОВАТЬ: Я изменил [j-1] на [j-i], чтобы он повторялся через каждую возможную пару. Кроме того, я решил проблему, используя алгоритм другого человека(правильный алгоритм), и получил тот же ответ, что и с моим алгоритмом. Возможно, это не самый быстрый и чистый код, но он работает!