算法-关于“给定的一个1,2,3组成的数字序列，求排成升序所需的最少交换次数”的算法题有两个很巧妙的解答，但是我没看懂，求大神解释！

Question

关于“给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数”这个算法有两个很巧妙的解答:
例如：
序列： 2 2 1 3 3 3 2 3 1
要变成
序列： 1 1 2 2 2 3 3 3 3
最少需要的交换次数为4。

解法一：
设 cAB 为在A位置上的B的数目，则答案为：
c21 + c31 + (c21 > c12 ? c23 + c21 - c12 : c32 + c12 - c21)
按照这一方法，再看上面那个例子：
c21 + c31 + (c21 > c12 ? c23 + c21 - c12 : c32 + c12 - c21)
=1 + 1 + ( 1 > 2 ? 2 + 1 - 2 : 1 + 2 - 1 )
=4
根据这个公式算得的答案为4，其他的例子我也测试过，确实是正确的。

解法二：
统计在应该是1的位置出现2的个数为a1;
统计在应该是2的位置出现1的个数为a2；
统计应该是1、2的位置出现3的个数为a3；
那么最少交换次数为：a3 + (a1 > a2 ? a1: a2)
果然根据这个公式算得的答案为4，其他的例子我也测试过，确实是正确的。

请问这两个方法中的公式是什么道理，为什么这样列？求详细解释！
关于这个算法题如果有更好的解答方法的话也欢迎回答！谢谢

Answer 1

将数字（或者别的什么东西）以任意方式重新排列的过程称为置换，置换总是可以唯一地写成若干个轮换的组合，所谓轮换是指a->b->c->d->a这样的a,b,c,d四个数循环着交换位置的过程，
比如说

a b c d e f g
c e f a g b d

就可以写成(acfbegd)

而
a b c d e f g
a e b c d g f
可以写成(a)(bedc)(fg)

而通过交换来完成某个置换的最小次数就等于通过交换完成这些轮换的次数，轮换长度为N的需要N-1次，因此总的次数就等于元素个数 - 轮换个数

回到原问题，显然就是找出一个置换，使得能将数列调整成目标状态，而且轮换个数最多。显然优先使用一轮换（不变），其次二轮换，最后是三轮换。
也就是：1-1、2-2、3-3的不交换（一轮换），1-2和2-1，1-3和3-1,2-3和3-2配对成二轮换，剩下的形成1-2-3或1-3-2的三轮换。最后的交换次数是二轮换的数量加上三轮换的数量乘以二。
用公式表示的话就是：
min(c12,c21) + min(c13,c31) + min(c23,c32) + |c12 - c21| * 2
（因为剩余的不能匹配的1-2或者2-1每个都会对应一个三轮换）

注意到min(c12,c21) + |c12 - c21| = max(c12,c21)
而
min(c12,c21) + max(c12,c21) = c12 + c21
因此
min(c12,c21) + max(c12,c21) = min(c12,c21) + min(c12,c21) + |c12 - c21|
= 2 * min(c12,c21) + |c12 - c21| = c12 + c21
同理
2 * min(c13,c31) + |c13 - c31| = c13 + c31
2 * min(c23,c32) + |c23 - c32| = c23 + c32

而
|c12 - c21| = |c13 - c31| = |c23 - c32|
（都是三轮换个数）
把前面三个等式左右两边分别相加得到：
2 * min(c12,c21) + 2 * min(c13,c31) + 2 * min(c23,c32) + 3 * |c12 - c21| = c12 + c21 + c13 + c31+ c23 + c32

因此
min(c12,c21) + min(c13,c31) + min(c23,c32) + |c12 - c21| * 2
= 0.5 * (c12 + c21 + c13 + c31+ c23 + c32 + |c23 - c32|)

然后：
注意到
c11 + c12 + c13 = 1的个数 = c11 + c21 + c31
因此
c12 + c13 = c21 + c31
因此
0.5 * (c12 + c21 + c13 + c31+ c23 + c32 + |c23 - c32|)
= c12 + c13 + 0.5 * (c23 + c32 + |c23 - c32|)
而由之前的结论：
c23 + c32 + |c23 - c32| = 2 * max(c23,c32)
因此
原式 = c12 + c13 + max(c23,c32)
和解法二等效（只不过1,2,3的顺序有差异）

而解法一：
c21 + c31 + (c21 > c12 ? c23 + c21 - c12 : c32 + c12 - c21)
由于c23 + c21 = c32 + c12，因此
原式 = c21 + c31 + c32 + c12 - min(c21,c12)
= c31 + c32 + (c21 + c12 - min(c21,c12))
= c31 + c32 + max(c21,c12)
可见也是等效的