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

[AustinLee]

有数组 A[1,2,3,4] B[2,3,1,4]
用什么算法可以 获取
以下数据结构
[1,2] [2,3] [3,1]
就是最后我可以获知哪些 数字被交换了
且交换的是哪些数据

我把题目换一下
数组 A[1,2,3,4] 交换为 B[2,3,1,4]
最少要交换 几次
分别要交换哪几个index
比如现在的例子
需要交换2次
首先交换 index 1 和 2
然后 交换 index 2 和 3

[clww]

结果应该不确定吧
一个简单的方案：从左到右读，A[i]!=B[i], A[i]==B[j], [A[i],A[j]]换

[AustinLee]

@clww 想想 在数学上确实 是不确定的
但是应该有个 最简的 就是交换次数最少的
算法 这样 我把题目换一下
数组 A[1,2,3,4] 交换为 B[2,3,1,4]
最少要交换 几次
分别要交换哪几个index

[lookhi]

自觉上要剪枝? 实际应该就直接交换就好了吧。
交换是独立的，对其他位置不定的没影响，也没啥好处吧

[sohoer]

Compute Levenshtein distance
跟这个算法有点关系

[AustinLee]

@lookhi 唉我数据结构完全没有概念
突然 发现 我现在有2个 数组 A[1,2,3] B[3,1,2]
应该怎么换的算法都写不出来了
你们不要拉着我 让我死了算了
@sohoer

[AustinLee]

@sohoer 这个 直接把我玩傻了 汗http://en.wikipedia.org/wiki/Levenshtein_distance

[sohoer]

@AustinLee 回头是岸

[wog]

其实，碰见这种问题，如果我实在做不出来都是用随机算法来做的
我试了下用随机算法来做，用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]

上面那个数字是需要交换的次数，为了节省空间，就没贴具体的交换方式

[wy315700]

根据数学原理 一个交换可以分割为若干个轮换的积 ，
然后接下来就简单了
一个长度为n的轮换 至少需要交换n-1次
因为轮换中除了最后一次交换，每次交换只能让一个数回到原位。(如果第n-k(k>=2)次交换有两个数回到原位，那么可以证明这个轮换能再次拆分成两个轮换)。
所以需要扫描一次，判断出轮换的个数t，最终结果就是 N-t，注：一个已经在原位的数也算一个轮换。
不知道这么算对不对
@AustinLee
@sohoer 和那个算法没多大关系，那个是最短编辑距离，允许增删改，这个问题是最小交换距离，只允许交换

[AustinLee]

@wy315700 我彻底斯巴达了 我查下资料试试

[wodesuck]

这是逆序对问题吧，用归并排序或者线段树都能在O（nlogn）解决

[AustinLee]

@wodesuck http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作
查了下 不对啦

[wy315700]

@AustinLee 看看这个吧
http://zh.wikipedia.org/wiki/%E7%BD%AE%E6%8F%9B
http://zh.wikipedia.org/wiki/%E5%AF%B9%E7%A7%B0%E7%BE%A4_(n%E6%AC%A1%E5%AF%B9%E7%A7%B0%E7%BE%A4)

[AustinLee]

@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]

@AustinLee 归并排序做一点小修改就可以求出逆序对了