計算排序一系列的1，2，3所需要的最少交換次數

即如111221331122312331....的序列
排序成111...222...333
如果我們知道應該把哪個元素放到哪個位置是正確的，就可以計算出最少交換次數。
但是我們不知道 ：）

想了兩種方法，第一種是錯的，第二種是對的。
一開頭以為greedy可以解決問題，即從兩端開始掃描，遇到3，1則進行交換
然後再重來，遇到2，3則進行交換。
這樣的方法可以達到幾乎最優，但是卻不是最優，考慮如下序列：

111...22333 222...1...1...222 333...1...1...1...333

上面方法會先把1裡面的2交換到3，最後會把這兩個2交換到2.... 裡面
然而最優的方法是直接放到2裡面。

這種方法對於只有1，2的序列是成立的。O(n)

第二種方法，基於數學計算。
假設1，2，3的個數各有n1,n2,n3個。
把這個序列看作三個bucket
顯然沒有排序前，這三個bucket裡面都有1，2，3.
最少的交換次數，說明不能有多餘交換，例如，把bucket1里本來應該放到bucket 2的2，先放到3，再放到2.
假設:
bucket 1里有的2，3分別為c12,c13
bucket 2里有的1，3分別為c21,c23
bucket 3里有的1，2分別為c31,c32

則最少交換次數是：min(c12,c21)+min(c13,c31)+ABS(c12-c21)+max(c23,c32)

這樣的式子還可以寫出好幾個，but why?

假設是以這樣一種方法進行交換，顯然可以做到最優：
bucket1 分別與 bucket2，bucket3進行交易，這種交易屬於最優的，因為它們一次直接交換了兩個元素到正確的位置。
而這種交換可以做min(c12,c21)+min(c13,c31)次。
注意c12與c21并不一定是相等的，因此，當交換完成后，1裡面可能剩下有2，或者是2裡面剩下1.
注意到有這樣的關係：
c12+c13 = c21+c31 => c12-c21=c31-c13
亦即：假設c12<c21，做完這種交換后，則bucket1里已經沒有2了，要把bucket2里剩餘的1放進去，必須用bucket1里的3來進行交換。
因此這部分的東西必須經過**兩次交換**才能放到正確的位置，即先把1里的3換2里的1，再把這個3放回到最終的bucket3里去。
這么一來bucket1已經完成了，而bucket2和bucket3此時的新的c23,c32肯定是相等的，因此還需進行c23次交換。
事實上上個公式也可以寫成：
min(c12,c21)+min(c13,c31)+min(c23,c32)+2*ABS(c12-c21)

最後的2*ABS(c12-c21)，正是必須進行兩次交換的元素個數。

原理很簡單，不過的確很考邏輯思維與IQ.