Search code examples
pythonlistdivide-and-conquer

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

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?

Solution

  • 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 :

    Hope this helps...