Fastest Algorithm to Find the Minimum Sum of Absolute Differences through List Rotation

Question

By rotating 2 lists either from left to right, Find the smallest possible sum of the absolute value of the differences between each corresponding item in the two lists given they're the same length.

Rotation Sample:

List [0, 1, 2, 3, 4, 5] rotated to the left = [1, 2, 3, 4, 5, 0]

List [0, 1, 2, 3, 4, 5] rotated to the right= [5, 0, 1, 2, 3, 4]

Sum of Absolute Difference:

List 1 = [1, 2, 3, 4]
List 2 = [5, 6, 7, 8]

Sum of Abs. Diff. = |1-5| + |2-6| + |3-7| + |4-8| = 16

Once again, for any arbitrary length of list and integer values, task is to look for the least possible sum by simply rotating to the left/right of either or both lists.

I had no problem with the rotation and acquiring of the minimum sum of absolute difference. I just want to know the smarter approach since my algorithm checks for every possible combination which is quite slow.

Here is my bruteforce approach:

list1 = [45, 21, 64, 33, 49]
list2 = [90, 12, 77, 52, 28]
choices = []                # Put all possible sums into a list to find the minimum value.
for j in range(len(list1)):  # List1 does a full rotation
    total = 0
    for k in range(len(list1)):
        total += abs(list1[k] - list2[k])
    list1.append(list1.pop(0))
    choices.append(total)
print(min(choices))

What's a smarter approach? I would appreciate a shorter code and time complexity as well.

I managed to make it faster by applying generators. Credits to @kuriboh for the idea! But since I'm still new in generator implementation, just want to know if this is the best way of implementing it to reduce my time complexity especially for my loop. Can we still go faster than this configuration?

list1 = [45, 21, 64, 33, 49]
list2 = [90, 12, 77, 52, 28]
choices = []
l = len(list1)
for j in range(l):
    total = sum([abs(int(list1[k])-int(list2[k])) for k in range(l)])
    list1.append(list1.pop(0))
    choices.append(total)
print(min(choices))

Answer 1

Since Python treats negative indexes as counting from the right end, you could sum the absolute value of list1 minus (list2 shifted by k) where 0 ≤ k < len(list1) as

sum(abs(list1[i] - list2[i - k]) for i in range(len(list1)))

If you want the minimum of all of these values

length = len(list1)
min(sum(abs(list1[i] - list2[i - k]) for i in range(length))
    for k in range(length))

This code is still O(n^2), but there is a lot less pushing and popping going on.

I really can't think of any way to make the algorithm faster than O(n^2).

Answer 2

An optimized mix of your original and Frank's accepted answer:

min(list1.append(list1.pop(0)) or
    sum(abs(x - y) for x, y in zip(list1, list2))
    for _ in list1)

Bit dirty to have the rotation in there like that, but hey, you're asking for "Fastest" :-)

Benchmark with lists of length 1000:

    original     Frank_Yellin   superb_rain  
     127 ms         164 ms         125 ms    
     140 ms         170 ms         117 ms    
     134 ms         166 ms         116 ms    
     124 ms         161 ms         126 ms    
     135 ms         164 ms         126 ms    

Benchmark code:

from timeit import repeat
from random import shuffle

def original(list1, list2):
    choices = []                # Put all possible sums into a list to find the minimum value.
    for j in range(len(list1)):  # List1 does a full rotation
        total = 0
        for k in range(len(list1)):
            total += abs(list1[k] - list2[k])
        list1.append(list1.pop(0))
        choices.append(total)
    return min(choices)

def Frank_Yellin(list1, list2):
    length = len(list1)
    return min(sum(abs(list1[i] - list2[i - k]) for i in range(length))
    for k in range(length))

def superb_rain(list1, list2):
    return min(list1.append(list1.pop(0)) or
               sum(abs(x - y) for x, y in zip(list1, list2))
               for _ in list1)

funcs = [
    (10, original),
    (10, Frank_Yellin),
    (10, superb_rain),
    ]

list1 = list(range(1000))
list2 = list1.copy()
shuffle(list2)

for _, f in funcs:
    print(f(list1, list2))

for _, f in funcs:
    print(f.__name__.center(15), end='')
print()

for _ in range(5):
    for number, f in funcs:
        t = min(repeat(lambda: f(list1, list2), number=number)) / number
        print('%8d ms    ' % (t * 1e3), end='')
    print()