最近在傳智論壇遇到一個算法的問題，想了一下，有一個我認為比較有趣的解法. 下面算 法或許不是最優的，但是可以參考一下.
=======================================================================
給定兩個字符串，僅由小寫字母組成，它們包含了相同字符。求把第一個字符串變
成第二個字符串的最小操作次數，且每次操作只能對第一個字符串中的某個字符移
動到此字符串中的開頭。
例如給定兩個字符串“abcd" "bcad" ，輸出：2，因為需要操作2次才能把"abcd"變
成“bcad" ，方法是：abcd->cabd->bcad。
我開始用廣度優先搜索做。可是比如abcdefg 和 gfedcba 遞歸下去就是7的7次方的
時間復雜度 然後再在變換位置的函數裡循環 循環次數報表。
然後我用List記錄 abcdefg出現的東東 把重復的去掉了，也就是7*6*5*4*3*2
但是每次判斷list.contain()在內部貌似又要循環時間和上面差不多.
有沒有比較好的解決方式.
========================================================================
這個問題比較有趣，這裡我使用C#來完成，主要是考慮微軟提供了許多數據結構 不用再重新實現數據結構和相關方法了.
再將原來的字符串看成一個等待排序的數據結構，就可以將問題簡化為簡單的排序算
法了. 即：指定序的排序問題.
舉個例子：將字符串"abcd"變成"bcad".
那麼字符集"bcad"構成一個有序集，可以得到映射表，如下：
{ ('b', 0), ('c', 1), ('a', 2), ('d', 3) }
因此需要排序的字符串就變成了一個數字集：{ 2, 0, 1, 3 }. 即
需要將這個數據集排序為 { 0, 1, 2, 3 }，需要求最小的步驟. 因
此將問題轉化為排序最小步驟問題.
另一方面，問題考慮了算法實現的要求，即每次只能將一個數據
取出，插入到開始的地方. 也就是說具體操作就是一個固定的函數：
將第i項插入到0項，原來前i-1項的數據依次後移一位. 故方法很簡單:
jk_remove([] s, temp = ( i = index - ; i >= ; i-- s[i + ] = s[] = }
那麼這個函數調用幾次，就表示操作了幾次.
下面考慮另一個問題. 就是什麼時候調用這個函數. 也就是如何操作才算是較優.
這個問題有點麻煩. 起初我打算從現成的算法中找一個. 不過現成的都不太友好. 想到
了使用"逆序"的方法.
所謂最少的步驟. 就是不要移動多余的步驟. 在前面已經提到，問題已經劃歸成排
序問題，下面姑且使用升序.
要將一個數字序列排序，又只能將數據往前放，那麼最小的步驟就是每次移動一個
數據並且這個數據就是一個良序的，也就是說這個數字不會再次移動. 那麼一個長度為
n的字符串，最多移動n-1次. 我想這個應該是最少的步驟了吧！！！
下面看看怎麼移動會比較好.
首先考慮移動的特征就是每次移動數據都放在最開始的地方. 同時下一次移動開始
後這個已經被移動過的數據就會自動擠到後面去. 那麼不再重復移動這個數據的辦法就
是首先移動最大的數. 那麼在移動剩下的最大數，就可以保證移動完成以後結果就是良
序的了.
那麼什麼樣的數據需要移動呢？很簡單逆序(注1)的. 舉個例子：
延續前面的例子，數字2013. 第一個數字不需要考慮，第二個數字0與2構成一個逆
序，因此0是逆序數. 第三個數字1與2構成逆序，即1為逆序數. 那麼首先移動較大的，
移動1得到1203. 由於數據排列發生變化，需要重新計算逆序. 因此得到0為逆序數，移
動0，得到結果0123.
這裡就得到一個結論，就是判斷逆序，移動最大的逆序數即可. 由此得到偽代碼：
jk_sort( temp = ;
( i = ; i < s.length; i++ ( j = ; j < i; j++
(s[i] <
(temp == || temp < temp =
(temp !=
}
這裡使用了遞歸，算法復雜度提升了，具體的優化可以以後再說. 那麼有了這個思
路以後，就可以實現了.
首先寫一個類
}
提供靜態方法，移動數據
jk_remove([] s, temp = ( i = index - ; i >= ; i-- s[i + ] = s[] = }
提供映射，可以考慮使用一個鍵值對
Dictionary<, > dic; JKSort( dic = Dictionary<, > ( i = ; i < chs.Length; i++ }
internal_jk_sort([] s, Dictionary<, > temp = -;
( i = ; i < s.Length; i++ ( j = ; j < i; j++
(dic[s[i]] <
(temp == - || dic[s[temp]] < temp =
(temp != -
}
實現對外公開的方法
JK_Sort( str, [] chs = [] obj =
JKSort j =
}
那麼就完成了排序. 這裡提供的算法沒有實現優化，如想了解優化與帶有重復字符
串的解決辦法，請等待下文.
睡覺，2013年12月18日凌晨0時.
注1
逆序：在一個數字排列中，如果其中的兩個數前面的一個比後面的一個大，那麼就稱
它們構成一個逆序. 相關逆序的結論與問題，可以參考《高等代數》或《線性代數》
的教材.
