Couple of points that are closer to each other in a list

Question

I have to do an algorithm, aprop, using divide and conquer to calculate the couple of points that are closer to each other in a list and also I have to calculate the complexity.

def aprop(a):
    longitudlista = len(a)
    if longitudlista <= 2:
        return a
    else:
        mig = longitudlista / 2
        pivot = (a[mig])

a= [1.2,2.9,3.1,4.0,5.7]

aprop(a)

Now I want that the algorithm return the couple of points that having the minimum difference of all the differences of all elements of the list using the pivot. How can i write this idea in code?

Answer 1

Sort your array and check pairwise for the smallest distance.

The sort can be done using a divide and conquer algorithm, like merge_sort in O(nlog(n)) time.

For instance you could piggyback on merge sort like this :

# For convenience of representation, assume pairs to be defined as 
# tuples of form ( no_1, no_2 )

def closest_pair(array):
    l = len(array)
    pivot = l/2

    if len(array) == 2:
        # Simply returns the pair
        return (array[0], array[1])

    if len(array) == 3:
        # Returns the pair which has the smallest distance amongst the 3C2 pairs
        return min(itertools.combinations(array, r = 2), key = lambda x : abs(x[1] - x[0]) )


    left_closest = closest_pair(array[:pivot])
    right_closest = closest_pair(array[pivot:])
    split_pair = (array[pivot-1], array[pivot]) # Just incase the split_pair is the closest

    return min(left_closest, right_closest, split_pair, key = lambda x : abs(x[1] - x[0]) )

For your array [1.2,2.9,3.1,4.0,5.7]

>>> closest_pair([1.2,2.9,3.1,4.0,5.7])
(2.9, 3.1)

Side Note:

If you don't care about the divide and conquer implementation, you could simply use min using a key and itertools.combinations ( Like implemented above for the combine step / the base case of len(array) equal to 3. )

>>> a = [1.2,2.9,3.1,4.0,5.7]
>>> min(itertools.combinations(a, r = 2), key = lambda x : abs(x[1] - x[0])))
(2.9, 3.1)

Check this to learn more about :

• itertools.combinations
• min with a key parameter - Has been explained for max but the same applies for min too.

Hope this helps...

Answer 2

The following code is General Implementation of the Divide and Conquer Scheme :

def divide_and_conquer(S, divide, combine): 
  if len(S) == 1: return S
  L, R = divide(S)
  A = divide_and_conquer(L, divide, combine)
  B = divide_and_conquer(R, divide, combine)
  return combine(A, B)

So based on the above algorithm you can use this :

from operator import sub

def divide_and_conquer(S, combine=[]):
    if len(S) == 2:
       combine.append(S)
    else :
       L, R = S[:(len(S)/2)+1],S[len(S)/2:]
       A = divide_and_conquer(L)
       B = divide_and_conquer(R)
       result=[abs(sub(i,j)) for i,j in combine]
       return combine[result.index(min(result))]

a= [1.2,2.9,3.1,4.0,5.7]

print divide_and_conquer(a)
[2.9, 3.1]