V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Sponsored by
LinkedIn
不坐班的神仙工作 · 去任何你想去的地方远程,赚一线城市的工资
2000 个不用出门 Social 的全球远程工作,帮助 V2EX 的小伙伴开启全新的工作方式。
Promoted by LinkedIn
AustinLee
V2EX  ›  问与答

想请教个数据结构问题 数学老师死的早

  •  
  •   AustinLee · 2013-03-29 11:33:37 +08:00 · 3173 次点击
    这是一个创建于 3473 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有数组 A[1,2,3,4] B[2,3,1,4]
    用什么算法可以 获取
    以下数据结构
    [1,2] [2,3] [3,1]
    就是最后我可以获知哪些 数字被交换了
    且交换的是哪些数据
    第 1 条附言  ·  2013-03-29 13:06:01 +08:00
    我把题目换一下
    数组 A[1,2,3,4] 交换为 B[2,3,1,4]
    最少要交换 几次
    分别要交换哪几个index
    比如现在的例子
    需要交换2次
    首先交换 index 1 和 2
    然后 交换 index 2 和 3
    16 条回复    1970-01-01 08:00:00 +08:00
    clww
        1
    clww  
       2013-03-29 11:45:38 +08:00
    结果应该不确定吧
    一个简单的方案:从左到右读,A[i]!=B[i], A[i]==B[j], [A[i],A[j]]换
    AustinLee
        2
    AustinLee  
    OP
       2013-03-29 13:04:56 +08:00
    @clww 想想 在数学上确实 是不确定的
    但是应该有个 最简的 就是交换次数最少的
    算法 这样 我把题目换一下
    数组 A[1,2,3,4] 交换为 B[2,3,1,4]
    最少要交换 几次
    分别要交换哪几个index
    lookhi
        3
    lookhi  
       2013-03-29 13:33:11 +08:00
    自觉上要剪枝? 实际应该就直接交换就好了吧。
    交换是独立的,对其他位置不定的没影响,也没啥好处吧
    sohoer
        4
    sohoer  
       2013-03-29 13:53:08 +08:00
    Compute Levenshtein distance
    跟这个算法有点关系
    AustinLee
        5
    AustinLee  
    OP
       2013-03-29 13:56:46 +08:00
    @lookhi 唉我数据结构完全没有概念
    突然 发现 我现在有2个 数组 A[1,2,3] B[3,1,2]
    应该怎么换的算法都写不出来了
    你们不要拉着我 让我死了算了
    @sohoer
    AustinLee
        6
    AustinLee  
    OP
       2013-03-29 15:23:57 +08:00
    @sohoer 这个 直接把我玩傻了 汗http://en.wikipedia.org/wiki/Levenshtein_distance
    sohoer
        7
    sohoer  
       2013-03-29 15:40:15 +08:00
    @AustinLee 回头是岸
    wog
        8
    wog  
       2013-03-30 17:26:04 +08:00
    其实,碰见这种问题,如果我实在做不出来都是用随机算法来做的
    我试了下用随机算法来做,用c++写了个小程序,(没看明白你那个题目是不是只能交换相邻的两个数字,不过我写程序是按照只能交换相邻位置的两个元素来写的)
    在数组长度小于6的时候都非常稳定,
    A[1,2,3,4] B[2,3,1,4]
    2
    real 0m0.291s
    user 0m0.008s
    sys 0m0.284s
    ====================
    A = {1, 2, 3, 4,5};
    B = {2, 3, 5, 1, 4};

    4
    real 0m0.295s
    user 0m0.008s
    sys 0m0.284s
    ========================
    A = {1, 2, 3, 4, 5, 6};
    B = {6, 2, 3, 5, 1, 4};
    11
    real 0m0.338s
    user 0m0.064s
    sys 0m0.272s
    在这之前,我程序的尝试次数定在1024,结果几乎没有什么浮动
    ======================
    A = {1, 2, 3, 4, 5, 6, 7};
    B = {6, 2, 7, 3, 5, 1, 4};
    17
    real 0m21.271s
    user 0m3.632s
    sys 0m17.616s
    在这里如果尝试次数还是1024的话,得到的结果浮动很大,所以直接改成65535了
    ==============================================
    A = {1, 2, 3, 4, 5, 6,7,8};
    B = {6, 2, 7, 3, 5, 8,1,4,};
    19
    real 0m19.241s
    user 0m1.596s
    sys 0m17.624s
    还是尝试65535次


    不过话说回来,这个问题用贪心算法和我用的这个方法,只能得到近似最优解,要真正准确的算出来最有解,还是得用动态规划,不过这个动态规划是需要完全遍历所有情况的,我觉得要实现的话不太现实
    wog
        9
    wog  
       2013-03-30 17:31:16 +08:00
    上面那个数字是需要交换的次数,为了节省空间,就没贴具体的交换方式
    wy315700
        10
    wy315700  
       2013-03-30 21:22:02 +08:00
    根据数学原理 一个交换可以分割为若干个轮换的积 ,
    然后接下来就简单了
    一个长度为n的轮换 至少需要交换n-1次
    因为轮换中除了最后一次交换,每次交换只能让一个数回到原位。(如果第n-k(k>=2)次交换有两个数回到原位,那么可以证明这个轮换能再次拆分成两个轮换)。
    所以需要扫描一次,判断出轮换的个数t,最终结果就是 N-t,注:一个已经在原位的数也算一个轮换。
    不知道这么算对不对
    @AustinLee
    @sohoer 和那个算法没多大关系,那个是最短编辑距离,允许增删改,这个问题是最小交换距离,只允许交换
    AustinLee
        11
    AustinLee  
    OP
       2013-04-01 09:24:04 +08:00
    @wy315700 我彻底斯巴达了 我查下资料试试
    wodesuck
        12
    wodesuck  
       2013-04-01 11:57:01 +08:00 via Android
    这是逆序对问题吧,用归并排序或者线段树都能在O(nlogn)解决
    AustinLee
        13
    AustinLee  
    OP
       2013-04-01 15:11:58 +08:00
    @wodesuck http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
    归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作
    查了下 不对啦
    AustinLee
        15
    AustinLee  
    OP
       2013-04-01 15:24:08 +08:00
    @lookhi
    A B
    |---| index |---| for(int i=0;A.length < i;i++){
    | 1 |<-- 0 -->| 3 | A[i] = B[i]
    |---| |---| }
    | 2 |<-- 1 -->| 1 | 额是不是 这样就OK了
    |---| |---|
    | 3 |<-- 2 -->| 2 |
    |---| |---|
    | 4 |<-- 3 -->| 4 |
    |---| |---|
    wodesuck
        16
    wodesuck  
       2013-04-01 15:48:58 +08:00
    @AustinLee 归并排序做一点小修改就可以求出逆序对了
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1940 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 70ms · UTC 05:09 · PVG 13:09 · LAX 22:09 · JFK 01:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.