- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我试图总结问题陈述如下:
给定 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
除此之外。
generator
这是
memory efficient
(确实如此),但作为生成器,我们也可以动态生成这些组合
iterate
在他们身上,估计 n=50,k=8 应该花费 140 多个小时 (:/)。
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
)。
algorithm
和
dynamic programming
下)
variance
和
unfairness sum
不是
perfectly
相关(它们是
strongly
相关的)这意味着在许多整数列表中,一个带有
minimum variance
的列表并不总是必须是
minimum unfairness sum
的列表.如果你想知道为什么,我实际上是在数学堆栈交换
HERE 上作为一个单独的问题问这个问题的。其中一位数学家为我证明了它(值得一看,因为这是出乎意料的)
最佳答案
您必须处理您的列表 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
关于python - 如何计算列表的最小不公平总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63774153/
我正在处理一组标记为 160 个组的 173k 点。我想通过合并最接近的(到 9 或 10 个组)来减少组/集群的数量。我搜索过 sklearn 或类似的库,但没有成功。 我猜它只是通过 knn 聚类
我有一个扁平数字列表,这些数字逻辑上以 3 为一组,其中每个三元组是 (number, __ignored, flag[0 or 1]),例如: [7,56,1, 8,0,0, 2,0,0, 6,1,
我正在使用 pipenv 来管理我的包。我想编写一个 python 脚本来调用另一个使用不同虚拟环境(VE)的 python 脚本。 如何运行使用 VE1 的 python 脚本 1 并调用另一个 p
假设我有一个文件 script.py 位于 path = "foo/bar/script.py"。我正在寻找一种在 Python 中通过函数 execute_script() 从我的主要 Python
这听起来像是谜语或笑话,但实际上我还没有找到这个问题的答案。 问题到底是什么? 我想运行 2 个脚本。在第一个脚本中,我调用另一个脚本,但我希望它们继续并行,而不是在两个单独的线程中。主要是我不希望第
我有一个带有 python 2.5.5 的软件。我想发送一个命令,该命令将在 python 2.7.5 中启动一个脚本,然后继续执行该脚本。 我试过用 #!python2.7.5 和http://re
我在 python 命令行(使用 python 2.7)中,并尝试运行 Python 脚本。我的操作系统是 Windows 7。我已将我的目录设置为包含我所有脚本的文件夹,使用: os.chdir("
剧透:部分解决(见最后)。 以下是使用 Python 嵌入的代码示例: #include int main(int argc, char** argv) { Py_SetPythonHome
假设我有以下列表,对应于及时的股票价格: prices = [1, 3, 7, 10, 9, 8, 5, 3, 6, 8, 12, 9, 6, 10, 13, 8, 4, 11] 我想确定以下总体上最
所以我试图在选择某个单选按钮时更改此框架的背景。 我的框架位于一个类中,并且单选按钮的功能位于该类之外。 (这样我就可以在所有其他框架上调用它们。) 问题是每当我选择单选按钮时都会出现以下错误: co
我正在尝试将字符串与 python 中的正则表达式进行比较,如下所示, #!/usr/bin/env python3 import re str1 = "Expecting property name
考虑以下原型(prototype) Boost.Python 模块,该模块从单独的 C++ 头文件中引入类“D”。 /* file: a/b.cpp */ BOOST_PYTHON_MODULE(c)
如何编写一个程序来“识别函数调用的行号?” python 检查模块提供了定位行号的选项,但是, def di(): return inspect.currentframe().f_back.f_l
我已经使用 macports 安装了 Python 2.7,并且由于我的 $PATH 变量,这就是我输入 $ python 时得到的变量。然而,virtualenv 默认使用 Python 2.6,除
我只想问如何加快 python 上的 re.search 速度。 我有一个很长的字符串行,长度为 176861(即带有一些符号的字母数字字符),我使用此函数测试了该行以进行研究: def getExe
list1= [u'%app%%General%%Council%', u'%people%', u'%people%%Regional%%Council%%Mandate%', u'%ppp%%Ge
这个问题在这里已经有了答案: Is it Pythonic to use list comprehensions for just side effects? (7 个答案) 关闭 4 个月前。 告
我想用 Python 将两个列表组合成一个列表,方法如下: a = [1,1,1,2,2,2,3,3,3,3] b= ["Sun", "is", "bright", "June","and" ,"Ju
我正在运行带有最新 Boost 发行版 (1.55.0) 的 Mac OS X 10.8.4 (Darwin 12.4.0)。我正在按照说明 here构建包含在我的发行版中的教程 Boost-Pyth
学习 Python,我正在尝试制作一个没有任何第 3 方库的网络抓取工具,这样过程对我来说并没有简化,而且我知道我在做什么。我浏览了一些在线资源,但所有这些都让我对某些事情感到困惑。 html 看起来
我是一名优秀的程序员,十分优秀!