向各位巨巨求一个算法

[ThunderEX]

有随便一个sorted数列比如：
[11356, 51308, 56246, 58316, 65360, 69866, 74806, 80104, 99488, 106486, 110695, 131901, 170195]
其中的数不重复，在一定范围内uniform distribution
希望从中抽取5个数，使得这5个数的任意两两之差的最小值尽可能大，换而言之就是使5个数尽可能分散。

要是枚举的话就有(200!)/(5!*195!)种组合，实在太多了。所以……有神马办法么？
如果哪里措辞不当什么的求轻拍……

[Xe0n0]

一维数轴上情况，相当于四个连续区间中最小区间长度最大。二分查找这个最小区间的长度，从数范围的四分之一开始二分。

每一次检验其实只有中间三个点需要尝试，最小和最大值都可以分别固定为数列的最小值和最大值，因为这不会比最优解更差。

因为数是正太分布的，所以区间移动的时候会跳过中间更多的点。应该比平均分布收敛得更快。我是这么觉得的。

[binux]

_list = sorted([11356, 51308, 56246, 58316, 65360, 69866, 74806, 80104, 99488, 106486, 110695, 131901, 170195])
a = [0, 1, 2, len(_list)-2, len(_list)-1]
max_a = None
max_d = 0

while a[1] < a[2] < a[3]:
_ a2_max_d = 0
_ #find pos for a[2]
_ while a[2] < a[3]:
__ a2_max_d = max(a2_max_d, min(_list[a[2]]-_list[a[1]], _list[a[3]]-_list[a[2]]))
__ a[2]+=1
_ tmp_min_d = min(_list[a[4]]-_list[a[3]], _list[a[1]]-_list[a[0]], a2_max_d)
_ if tmp_min_d > max_d:
__ max_d = tmp_min_d
__ max_a = list(a)

_ #move a1 or a3
_ if _list[a[4]]-_list[a[3]] > _list[a[1]]-_list[a[0]]:
__ a[1]+=1
__ a[2]=a[1]+1
_ else:
__ a[3]-=1
__ a[2]=a[1]+1

print [_list[x] for x in a], max_d

[ThunderEX]

@Xe0n0
不过……如果是取6个点而不是5个点还有办法么？
还有……是均匀分布的……

[ThunderEX]

@binux
这个缩进好！
不过我穷举粗来是这个：[11356, 51308, 99488, 131901, 170195]
代码好长我慢慢看=.=

[binux]

@ThunderEX 有些细节错误

_list = sorted([11356, 51308, 56246, 58316, 65360, 69866, 74806, 80104, 99488, 106486, 110695, 131901, 170195])
a = [0, 1, 2, len(_list)-2, len(_list)-1]
max_a = None
max_d = 0

while a[1] < a[2] < a[3]:
_ a2_max_d = 0
_ a2_pos = a[2]
_ #find pos for a[2]
_ while a[2] < a[3]:
__ if a2_max_d < min(_list[a[2]]-_list[a[1]], _list[a[3]]-_list[a[2]]):
___ a2_pos = a[2]
___ a2_max_d = min(_list[a[2]]-_list[a[1]], _list[a[3]]-_list[a[2]])
__ a[2]+=1
_ tmp_min_d = min(_list[a[4]]-_list[a[3]], _list[a[1]]-_list[a[0]], a2_max_d)
_ if tmp_min_d > max_d:
__ a[2] = a2_pos
__ max_d = tmp_min_d
__ max_a = list(a)

_ #move a1 or a3
_ if _list[a[4]]-_list[a[3]] > _list[a[1]]-_list[a[0]]:
__ a[1]+=1
__ a[2]=a[1]+1
_ else:
__ a[3]-=1
__ a[2]=a[1]+1

print [_list[x] for x in max_a], max_d

[ThunderEX]

@binux
明白了！效果拔群！谢谢谢谢~

[kuphrer]

动态规划

[juicy]

"这5个数的任意两两之差的最小值尽可能大"+这5个数已排序

<====>

第5个数与第1个数的差值最大？

那就是说循环求出第5个和第1个，第6个和第2个，第7个和第3个，...的差值，比较一下哪个最大就行了？只有O(n)的复杂度。。即使是没排序的，通过merge sort，也能达到O(nlogn)的效率。。

不知道我这样理解对不对。。是不是想简单了？。。。

[juicy]

汗。。。第一条就不成立。。。我说怎么会这么简单。。。太冒失了。。。。。

[ThunderEX]

@juicy 我也没看懂你的囧……
我的意思就是在sorted的情况下使得min([trks[i+1] - trks[i] for i in range(len(trks) - 1)])最大就好了

[Xe0n0]

@ThunderEX 也可以一样做吧。看成了 Normal Distribution 不好意思。