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

Question

我曾试图将问题陈述归纳如下：

给定n、k和数组(列表) arr，其中n = len(arr)和k是set (1, n) inclusive中的integer。

对于数组(或列表) myList，不公平和定义为myList中所有可能对之间的绝对差异(每个组合有2个元素)的sum。

解释：如果mylist = [1, 2, 5, 5, 6]，那么最小的不公平和或毛里求斯。请注意，元素在列表中的index被认为是唯一的，而不是它们的值。

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

如果你真的需要看问题陈述，那就是这里

我的目标

考虑到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个小时(:/)。

我在所以这里上发布了同样的问题(您可能想看一看，以便正确地理解我--它通过融合进行了讨论，并给出了一个答案，这使我想到了我的第二种方法--更好的方法(我应该说融合的方法是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秒是10000之外的n个测试用例的限制:/ )而终止的(最大的测试用例有n=100000)。

=====

您将如何处理这个问题，以便在给定的时间限制(5秒)内处理所有测试用例？(问题列在algorithm &dynamic programming下)

(关于你的推荐信，你可以看看

1. 成功提交(py3，py2，C++，java)在这个问题上得到了其他候选人的支持--，这样你就可以为我和未来的访问者解释这个方法了。
2. 社论由问题集者解释如何处理这个问题
3. 解决方案代码由问题策划人自己(py2，C++)编写。
4. 输入数据(测试用例)和预期输出

Edit1 :：

对于这个问题的未来访客，我到目前为止的结论是，

variance和unfairness sum与perfectly无关(它们与strongly相关)，这意味着在许多整数列表中，带有minimum variance的列表不一定总是与minimum unfairness sum相关的列表。如果你想知道为什么，我实际上问了一个关于数学堆栈交换这里的单独问题，其中一位数学家为我证明了这一点，xD (值得一看，因为这是意外的)

就整个问题而言，您可以在下面阅读archer & Attersson的答案(仍然试图找出一种天真的方法来实现这一目标--不过，现在应该不远了)

(谢谢你的帮助或建议:)

Answer 1

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

1. 必须对原始数组进行排序。它的复杂性为O(NlogN)
2. 此时，您可以检查连续的子数组，因为非连续的子数组会导致更差(或等于，但不是更好)的“不公平和”。阿切尔的回答也解释了这一点。
3. 最后一次检查，找出最小“不公平和”可以在O(N)中进行。你需要为每一个连续的k长子阵计算美国。错误是对在O(k)中完成的每一步进行重新计算，这就给O(k*N)带来了复杂性。这可以用O(1)来完成，正如你贴出的社论所显示的，包括数学公式。它需要在步骤1之后对累积数组进行先前的初始化(在O(N)中完成，空间复杂度也是O(N) )。

它可以工作，但由于n<=10000超时而终止。

(来自对阿切尔问题的评论)

要解释步骤3，请考虑k= 100。您正在滚动N长数组和第一次迭代，您必须像往常一样计算子数组的US值，从0元素到99元素，需要100段。下一步需要对仅与前一个元素1到100不同的子数组计算相同的值。然后，2到101等，如果它有帮助，把它想象成一条蛇。一个块被移除，另一个被添加。不需要执行整个O(k)滚动。就像社论中解释的那样，把数学算出来，你就用O(1)来做。

因此，由于第一类的原因，最终的复杂度将是O(NlogN)。

Answer 2

您必须对您的列表进行排序，并且只检查具有连续元素的子列表。这是因为在默认情况下，任何包含至少一个非连续元素的子列表都会有更高的不公平和。

例如，如果列表是

1, 3，7,10,20 ,35,100,250,2000,5000并且要检查长度为3的子列表，那么解必须是1,3,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