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

Question

我试图将问题陈述总结如下::

给定 n、k 和一个数组（列表）arr，其中 n = len(arr) 和 k 是 integer set (1, n) inclusive.

对于数组（或列表）myList，不公平总和定义为 myList.

解释：如果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

我的Objective

给定 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 上发布了与问题相同的问题（您可能想看一看以正确理解我 - 它有讨论和融合的答案，这将我带到我的第二种方法 - 更好的方法（我应该说融合的方法 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) 其他候选人关于这个问题 - 这样你就可以为我和未来的访客解释这种方法)
an editorial 由问题 setter 解释如何处理问题
a solution code 问题 setter 他自己 (py2, C++).
Input data (test cases) and expected output

编辑 1 ::

对于这个问题的未来访问者，我现在的结论是，
variance 和 unfairness sum 不 perfectly 相关（它们是 strongly 相关）这意味着在许多整数列表中，具有 minimum variance 的列表不' 总是必须是带有 minimum unfairness sum 的列表。如果你想知道为什么，我实际上是作为一个关于数学堆栈交换的单独问题问的 HERE 其中一位数学家为我证明了它 xD（值得一看，因为它出乎意料）

就问题的整体而言，您可以阅读下面 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

Answer 2

我看到这个问题还没有完整的答案。我会写一个正确的算法的轨道，它将通过判断。为了尊重 Hackerrank 挑战的目的，我不会写代码。因为我们有可行的解决方案。

原数组必须排序。这具有 O(NlogN)
的复杂性
此时您可以检查连续的子数组，因为 non-consecutive 子数组会导致更差（或相等，但不会更好）的“不公平总和”。这在 archer 的回答中也有解释
最后的检查段落，找到最小的“不公平和”可以在O(N)内完成。您需要为每个连续的 k-long 子数组计算 US。错误是在 O(k) 中完成的每一步都重新计算它，这使这段话的复杂度达到了 O(k*N)。正如您发布的社论所示，它可以在 O(1) 中完成，包括数学公式。它需要在步骤 1 之后对累积数组进行预先初始化（在 O(N) 中完成，space 复杂度也为 O(N)）。

It works but terminates due to time out for n<=10000.

（来自对 archer 问题的评论）

为了解释第 3 步，考虑 k = 100。您正在滚动 N-long 数组和第一次迭代，您必须照常计算从元素 0 到 99 的子数组的 US，需要 100段落。下一步需要您计算一个子数组，该子数组仅与前一个元素相差 1 个元素 1 到 100。然后是 2 到 101，依此类推。如果有帮助，请把它想象成一条蛇。删除一个块并添加一个。不需要执行整个 O(k) 滚动。只需按照社论中的说明计算数学，您将在 O(1) 中完成。

因此，由于第一次排序，最终的复杂度将渐近为 O(NlogN)。

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

how to calculate the minimum unfairness sum of a list

python

arrays

algorithm

dynamic-programming