python - 如何计算列表的最小不公平总和

Question

我试图总结问题陈述如下:
给定 n , k和一个数组(一个列表)arr哪里n = len(arr)和 k是 integer在 set (1, n) inclusive .
对于数组(或列表)myList , 不公平总和定义为 sum myList 中所有可能对(每个组合有 2 个元素)之间的绝对差异.
解释 : 如果 mylist = [1, 2, 5, 5, 6]那么最小不公平金额或 MUS。请注意，元素被认为是独一无二的 index在列表中不是他们的值

MUS = |1-2| + |1-5| + |1-5| + |1-6| + |2-5| + |2-5| + |2-6| + |5-5| + |5-6| + |5-6|

如果你真的需要看问题陈述，它是HERE
我的目标
给定 n, k, arr (如上所述)，找到 Minimum Unfairness Sum在每个 len(sub array) = k 的约束下，所有可能的子数组的不公平总和[这是让我们的生活更轻松的一件好事，我相信:)]
我试过的
好吧，这里有很多东西要添加，所以我会尽量简短。
我的第一种方法 这是我使用的地方 itertools.combinations获得所有可能的组合和 statistics.variance检查其 spread of data (是的，我知道我一团糟)。
在您看到下面的代码之前，您是否认为这些方差和不公平总和是完全相关的(我知道它们是强相关的)，即带有 minimum variance 的子数组吗？必须是 MUS 的子数组??
您只需查看 LetMeDoIt(n, k, arr)功能。如果您需要 MCVE ，检查下面的第二个代码片段。

from itertools import combinations as cmb
from statistics import variance as varn

def LetMeDoIt(n, k, arr):
    v = []
    s = []
    subs = [list(x) for x in list(cmb(arr, k))]  # getting all sub arrays from arr in a list

    i = 0
    for sub in subs:
        if i != 0:
            var = varn(sub)  # the variance thingy
            if float(var) < float(min(v)):
                v.remove(v[0])
                v.append(var)
                s.remove(s[0])
                s.append(sub)
            else:
                pass

        elif i == 0:
            var = varn(sub)
            v.append(var)
            s.append(sub)
            i = 1

    final = []
    f = list(cmb(s[0], 2))  # getting list of all pairs (after determining sub array with least MUS)
    
    for r in f:
        final.append(abs(r[0]-r[1]))  # calculating the MUS in my messy way

    return sum(final)

以上代码适用于 n<30但提出了MemoryError除此之外。
在 Python 聊天中，Kevin 建议我尝试 generator这是 memory efficient (确实如此)，但作为生成器，我们也可以动态生成这些组合 iterate在他们身上，估计 n=50，k=8 应该花费 140 多个小时 (:/)。
我在 SO HERE 上发布了与问题相同的问题(您可能想看看以正确理解我 - 它有讨论和融合的答案，这将我带到我的第二种方法 - 更好的方法(我应该说融合的方法 xD))。
第二种方法

from itertools import combinations as cmb

def myvar(arr):   # a function to calculate variance
    l = len(arr)
    m = sum(arr)/l
    return sum((i-m)**2 for i in arr)/l

def LetMeDoIt(n, k, arr):
    sorted_list = sorted(arr)  # i think sorting the array makes it easy to get the sub array with MUS quickly
    variance = None
    min_variance_sub = None
    
    for i in range(n - k + 1):
        sub = sorted_list[i:i+k]
        var = myvar(sub)
        if variance is None or var<variance:
            variance = var
            min_variance_sub=sub
            
    final = []
    f = list(cmb(min_variance_sub, 2))  # again getting all possible pairs in my messy way

    for r in f:
        final.append(abs(r[0] - r[1]))

    return sum(final)

def MainApp():
    n = int(input())
    k = int(input())

    arr = list(int(input()) for _ in range(n))

    result = LetMeDoIt(n, k, arr)

    print(result)    

if __name__ == '__main__':
    MainApp()

此代码适用于 n up to 1000 (可能更多)，但由于 time out 而终止(5 秒是在线判断的限制:/)对于 n 超出 10000 (最大的测试用例有 n=100000 )。
======
您将如何处理此问题以在给定的时间限制(5 秒)内处理所有测试用例？ (问题列在 algorithm 和 dynamic programming 下)
(对于您的引用，您可以查看

successful submissions (py3, py2, C++, java) 其他候选人对此问题的评论 - 这样你就可以
为我和 future 的访客解释这种方法 )

an editorial由问题制定者解释如何解决问题

a solution code由问题设置者本人(py2，C++)。

Input data (test cases) and expected output

编辑 1::
对于这个问题的 future 访问者，我到目前为止的结论是，
那个variance和 unfairness sum不是 perfectly相关(它们是 strongly 相关的)这意味着在许多整数列表中，一个带有 minimum variance 的列表并不总是必须是 minimum unfairness sum 的列表.如果你想知道为什么，我实际上是在数学堆栈交换HERE 上作为一个单独的问题问这个问题的。其中一位数学家为我证明了它(值得一看，因为这是出乎意料的)
就整个问题而言，您可以阅读下面的 archer & Attersson 的答案(仍在尝试找出一种天真的方法来执行此操作 - 不过现在应该不远了)

感谢您的任何帮助或建议:)

Answer 1

您必须处理您的列表 SORTED 并仅检查具有连续元素的子列表。这是因为默认情况下，任何包含至少一个不连续元素的子列表将具有更高的不公平性总和。
例如，如果列表是
[1,3,7,10,20,35,100,250,2000,5000] 并且您想检查长度为 3 的子列表，则解决方案必须是 [1,3,7] [3,7,10] [7] 之一,10,20] 等
任何其他子列表，例如 [1,3,10] 将具有更高的不公平总和，因为 10>7 因此它与其余元素的所有差异都将大于 7
[1,7,10](左侧不连续)与 1<3 相同
鉴于此，您只需检查长度为 k 的连续子列表，这显着减少了执行时间
关于编码，这样的事情应该有效:

def myvar(array):
    return sum([abs(i[0]-i[1]) for i in itertools.combinations(array,2)])  
  
def minsum(n, k, arr):
        res=1000000000000000000000 #alternatively make it equal with first subarray
        for i in range(n-k):
            res=min(res, myvar(l[i:i+k]))
        return res