Питон "Круглый Робин" - PullRequest
Новая
       11

Питон "Круглый Робин"

4 голосов
/ 08 апреля 2009

Учитывая несколько (x, y) упорядоченных пар, я хочу сравнить расстояния между каждой из них. Итак, представьте, что у меня есть список упорядоченных пар: 

pairs = [a,b,c,d,e,f]

У меня есть функция, которая берет две упорядоченные пары и находит расстояние между ними: 

def distance(a,b):
    from math import sqrt as sqrt
    from math import pow as pow
    d1 = pow((a[0] - b[0]),2)
    d2 = pow((a[1] - b[1]),2)
    distance = sqrt(d1 + d2)
    return distance

Как я могу использовать эту функцию для сравнения каждой упорядоченной пары с любой другой упорядоченной парой, в конечном итоге найдя две упорядоченные пары с наибольшим расстоянием между ними?

Psuedopsuedocode: 

     distance(a,b)
     distance(a,c)
     ...
     distance(e,f)

Любая помощь будет принята с благодарностью.

Ответы [ 5 ]

17 голосов
/ 08 апреля 2009

в Python 2.6, вы можете использовать itertools.permutations 

import itertools
perms = itertools.permutations(pairs, 2)
distances = (distance(*p) for p in perms)

или 

import itertools
combs = itertools.combinations(pairs, 2)
distances = (distance(*c) for c in combs)
10 голосов
/ 08 апреля 2009 
try:

    from itertools import combinations

except ImportError:

    def combinations(l, n):
        if n != 2: raise Exception('This placeholder only good for n=2')
        for i in range(len(l)):
            for j in range(i+1, len(l)):
                yield l[i], l[j]


coords_list = [(0,0), (3,4), (6,8)]

def distance(p1, p2):
    return ( ( p2[0]-p1[0] ) ** 2 + ( p2[1]-p1[1] )**2 ) ** 0.5

largest_distance, (p1, p2) = max([
     (distance(p1,p2), (p1, p2)) for (p1,p2) in combinations(coords_list, 2)
     ])


print largest_distance, p1, p2
6 голосов
/ 08 апреля 2009

Попробуйте: 

max(distance(a, b) for (i, a) in enumerate(pairs) for b in pairs[i+1:])

Это позволяет избежать сравнения идентичностей (например, distance(x, x), distance(y, y) и т. Д.). Это также избегает симметричных сравнений, так как distance(x, y) == distance(y, x).

<Ч />

Обновление: Мне нравится Решение Евгения , чтобы использовать itertools немного лучше, поскольку оно выражает то, что вы пытаетесь сделать более лаконично. Оба наших решения делают то же самое. (Примечание: убедитесь, что вы используете комбинаций , а не перестановок - это будет намного медленнее!)

4 голосов
/ 08 апреля 2009

немного связано, вам не нужно самостоятельно вычислять евклидово расстояние, есть математика. Hypot: 

In [1]: a = (1, 2)
In [2]: b = (4, 5)
In [3]: hypot(a[0]-b[0], a[1]-b[1])
Out[3]: 4.2426406871192848
3 голосов
/ 08 апреля 2009

Если вы не возражаете против вычисления расстояния между двумя одинаковыми точками, следующее найдет наибольшее расстояние: 

max( [distance(a, b) for a in pairs for b in pairs] )

Чтобы вместо этого иметь пары a и b, выполните следующие действия: 

import operator
max( [((a,b), distance(a, b)) for a in pairs for b in pairs], key=operator.itemgetter(1))

Вы можете объединить это с решением Джона Феминеллы, чтобы получить кортеж (a, b) без сравнения избыточных расстояний

...