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?
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]