通过列表轮换找到最小绝对差和的最快算法

Question

通过从左到右旋转 2 个列表，找到两个列表中每个对应项之间差异的绝对值的最小可能总和，因为它们的长度相同。

旋转样品：

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]

绝对差之和：

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

再一次，对于任意长度的列表和整数值，任务是通过简单地旋转到一个或两个列表的左/右来寻找最小的总和。

我对旋转和获取最小绝对差和没有问题。我只想知道更聪明的方法，因为我的算法会检查每个可能的组合，这很慢。

这是我的蛮力方法：

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))

什么是更聪明的方法？我也希望能有更短的代码和时间复杂度。

我设法通过应用生成器使其更快。感谢@kuriboh 的想法！但是由于我在生成器实现方面还是新手，只想知道这是否是实现它以减少我的时间复杂度的最佳方式，尤其是对于我的循环。我们还能比这个配置更快吗？

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

我还没有解决完整的问题，但在输入值全部为0或1（或任何两个不同的值，或任何O(1)不同的值，但我们需要另一个想法来进一步解决）的特殊情况下，我们可以O(n log n)通过应用快速卷积得到 -time 算法。

这个想法是计算所有绝对差之和，List1 * reverse(1 - List2) + (1 - List1) * reverse(List2)其中1 - List表示逐点执行该操作并表示循环卷积（可使用一对 FFT*及时计算）。O(n log n)这里循环卷积的定义是

             n-1
             __
             \
(f * g)(i) = /_  f(j) g((i - j) mod n).
             j=0

替换List1和f，我们reverse(1 - List2)得到g

                                  n-1
                                  __
                                  \
(List1 * reverse(1 - List2))(i) = /_ List1(j) (1 - List2((n-1-(i-j)) mod n))
                                  j=0

                                  n-1
                                  __
                                  \
                                = /_ List1(j) (1 - List2((j-(i+1)) mod n)).
                                  j=0

产品List1(j) (1 - List2((j-(i+1)) mod n))是1当且仅当List1(j) = 1和List2((j-(i+1)) mod n) = 0，0否则。因此，卷积的值计算了具有 的位置的左侧循环偏移的i位置的数量。另一个卷积计数s对应于s。考虑到我们的输入限制，这是绝对差值之和。List11i+1List2001

代码：

import numpy


def convolve_circularly(a1, a2):
    return numpy.round(numpy.abs(numpy.fft.ifft(numpy.fft.fft(a1) * numpy.fft.fft(a2))))


def min_sum_abs_diff(a1, a2):
    a1 = numpy.array(a1)
    a2 = numpy.array(a2)[::-1]
    return numpy.min(convolve_circularly(a1, 1 - a2) + convolve_circularly(1 - a1, a2))


def slow_min_sum_abs_diff(a1, a2):
    return min(
        sum(abs(a1[i] - a2[i - k]) for i in range(len(a1))) for k in range(len(a2))
    )


def main():
    n = 100
    for r in range(100000):
        a1 = numpy.random.randint(2, size=n)
        a2 = numpy.random.randint(2, size=n)
        r = min_sum_abs_diff(a1, a2)
        slow_r = slow_min_sum_abs_diff(a1, a2)
        if r != slow_r:
            print(a1, a2, r, slow_r)
            break


if __name__ == "__main__":
    main()