Reorder a list so that the total consecutive difference between two elements is the smallest possible

Question

Say we have a list. How can we reorder it so that the total difference between two consecutive elements is the smallest possible? For example, list = [7, 4, 2, 6]. The differences between two consecutive elements are 3,2,4 Therefore, the total difference is 9. We can rearrange it to become [2, 4, 6, 7] (not sorting) The differences between two consecutive elements are 2,2,1 Therefore, the total difference is 5.

I already created a function to calculate the total difference of a list.

def total_diff(test_list):
    t = 0
    for i in range(1, len(test_list)):
        t += test_list[i] - test_list[i-1]
    return t

What should I do next?

Answer 1

Your total_diff function needs to compute the sum of the aboslute values of the differences:

def total_diff(test_list):
    t = 0
    for i in range(1, len(test_list)):
        t += abs(test_list[i] - test_list[i-1])
    return t

Otherwise, the differences are a telescoping series whose sum depends only on the first and last elements of the list.

TD(L) = (L[1] - L[0]) + (L[2] - L[1]) + (L[3] - L[2]) + ... + (L[n-1] - L[n-2])
      = -L[0] + (L[1] - L[1]) + (L[2] - L[2]) + ... + (L[n-1] - L[n-2])
      = -L[0] + L[n-1]