V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
ThunderEX
V2EX  ›  问与答

向各位巨巨求一个算法

  •  
  •   ThunderEX · 2013-07-25 21:33:58 +08:00 · 3473 次点击
    这是一个创建于 3899 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有随便一个sorted数列比如:
    [11356, 51308, 56246, 58316, 65360, 69866, 74806, 80104, 99488, 106486, 110695, 131901, 170195]
    其中的数不重复,在一定范围内uniform distribution
    希望从中抽取5个数,使得这5个数的任意两两之差的最小值尽可能大,换而言之就是使5个数尽可能分散。

    要是枚举的话就有(200!)/(5!*195!)种组合,实在太多了。所以……有神马办法么?
    如果哪里措辞不当什么的求轻拍……
    11 条回复    1970-01-01 08:00:00 +08:00
    Xe0n0
        1
    Xe0n0  
       2013-07-25 22:20:41 +08:00   ❤️ 1
    一维数轴上情况,相当于四个连续区间中最小区间长度最大。二分查找这个最小区间的长度,从数范围的四分之一开始二分。

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

    因为数是正太分布的,所以区间移动的时候会跳过中间更多的点。应该比平均分布收敛得更快。我是这么觉得的。
    binux
        2
    binux  
       2013-07-25 22:33:57 +08:00   ❤️ 1
    _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
        3
    ThunderEX  
    OP
       2013-07-25 23:08:16 +08:00
    @Xe0n0
    不过……如果是取6个点而不是5个点还有办法么?
    还有……是均匀分布的……
    ThunderEX
        4
    ThunderEX  
    OP
       2013-07-25 23:09:45 +08:00
    @binux
    这个缩进好!
    不过我穷举粗来是这个:[11356, 51308, 99488, 131901, 170195]
    代码好长我慢慢看=.=
    binux
        5
    binux  
       2013-07-25 23:17:35 +08:00   ❤️ 1
    @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
        6
    ThunderEX  
    OP
       2013-07-25 23:28:13 +08:00
    @binux
    明白了!效果拔群!谢谢谢谢~
    kuphrer
        7
    kuphrer  
       2013-07-25 23:36:28 +08:00
    动态规划
    juicy
        8
    juicy  
       2013-07-25 23:51:37 +08:00
    "这5个数的任意两两之差的最小值尽可能大"+这5个数已排序

    <====>

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

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

    不知道我这样理解对不对。。是不是想简单了?。。。
    juicy
        9
    juicy  
       2013-07-26 00:01:10 +08:00   ❤️ 1
    汗。。。第一条就不成立。。。我说怎么会这么简单。。。太冒失了。。。。。
    ThunderEX
        10
    ThunderEX  
    OP
       2013-07-26 00:01:30 +08:00
    @juicy 我也没看懂你的囧……
    我的意思就是在sorted的情况下使得min([trks[i+1] - trks[i] for i in range(len(trks) - 1)])最大就好了
    Xe0n0
        11
    Xe0n0  
       2013-07-26 09:12:34 +08:00   ❤️ 1
    @ThunderEX 也可以一样做吧。看成了 Normal Distribution 不好意思。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2869 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:11 · PVG 21:11 · LAX 06:11 · JFK 09:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.