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

算法:在给定的操作方法内,如何用最少的步数将一个列表排序成另外一个大小相同的列表。

  •  
  •   TJT · 2017-02-11 16:45:53 +08:00 · 1491 次点击
    这是一个创建于 1074 天前的主题,其中的信息可能已经有所发展或是发生改变。

    起因

    产品中有个用户排名列表(大小固定),于是有了个新的需求,这个列表要定时刷新,并且发生变化的用户高亮一下。 起初一看,不难嘛,位置变了就算发生变化了。但是有这种情况,有个用户突然插入到了列表的开头,那么对于剩下的用户来说,他们在列表中的位置都发生了变化,但这显然不符合常理,应该是只有刚插入的那个用户算是变化了,于是就展开了后面更复杂的情况。。。

    可能的情况

    旧列表 => 新列表 = {发生变化的下标集合}

    1. [1, 2, 3, 4, 5] => [1, 2, 3, 4, 9] = {4}
    2. [1, 2, 3, 4, 5] => [1, 2, 5, 4, 3] = {2, 4}
    3. [1, 2, 3, 4, 5] => [0, 1, 2, 3, 4] = {0}
    4. [1, 2, 3, 4, 5] => [3, 4, 5, 1, 2] = {3, 4}
    5. [1, 2, 3, 4, 5] => [0, 1, 4, 3, 2] = {0, 2, 4}
    6. [1, 2, 3, 4, 5] => [3, 1, 2, 4, 5] = {0}
      ...

    方案 0

    用排序算法,记录排序算法的对列表的所有修改,然后体现到界面上。在进一步优化可以针对数据特征来改进排序算法,但经过我们的讨论,这个方案很难接近最优解。

    方案 1

    定义以下操作

    • Swap(a, b): Exchange location of a and b.
    • Insert(x): Insert new item at index x, and delete last item.
    • MoveSeq(startIndex, length, targetIndex): Move array at startIndex with length(min=1) to targetIndex.

    最后问题就是:如何用最少的操作来将 A 列表变成 B 列表

    首先考虑的是穷举,但最后发现不能用穷举来解决,因为没有边界来确定是否已经穷举完所有可能,并且目前的情况下,可能性是无限的。

    然后想到用 GP( https://en.wikipedia.org/wiki/Genetic_programming) 来接近最优解,但这个实现难度也不小。

    问题

    1. 这个问题对应的是那个具体领域? Permutation or Sort algorithm?
    2. 有什么别的方法更简单粗暴?

    最后

    其实这个需求不是很重要,排名的变化是很有特征的,只要针对大部分出现的情况进行处理就好,就算没有处理到实际上也没什么影响。但这个问题本身我觉得是很有趣的,而且难度也不小,所以想看下大家对这个问题的解决思路,互相学习下~

    先谢谢大家,第一次在 V2EX 发这么长的帖子,写的不好的地方请见谅。希望能看到脑洞大开的思路 XD

    6 回复  |  直到 2017-02-11 18:58:42 +08:00
    slixurd
        1
    slixurd   2017-02-11 16:48:21 +08:00   ♥ 1
    Levenshtein distance?
    TJT
        2
    TJT   2017-02-11 16:52:26 +08:00
    @slixurd 谢谢!没有了解过这个,我研究下
    aheadlead
        3
    aheadlead   2017-02-11 17:15:44 +08:00 via iPhone   ♥ 1
    看了几遍不是很明白
    需要一些样例来说明

    看标题立即就想到了 1#说的编辑距离
    这是高中时的一道经典动态规划的题目

    同建议看看 1#的内容
    aheadlead
        4
    aheadlead   2017-02-11 17:16:36 +08:00 via iPhone
    看了几遍不是很明白,需要一些样例来说明。看标题立即就想到了 1#说的编辑距离,这是高中时的一道经典动态规划的题目。同建议看看 1#的内容。
    TJT
        5
    TJT   2017-02-11 17:25:14 +08:00 via Android
    @aheadlead 嗯,谢谢,我已经试着用 Levenshtein distance 的算法来实现这个需求了。另外是 #可能的情况 里面的样例不够直观导致你不是很明白吗?
    Exin
        6
    Exin   2017-02-11 18:58:42 +08:00 via iPhone   ♥ 1
    参考下 git diff 这种功能的思路?
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2690 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 05:59 · PVG 13:59 · LAX 21:59 · JFK 00:59
    ♥ Do have faith in what you're doing.