前兩天看到了這篇帖子：看到的兩道面試題，裡面的第二道題非常有代表性， 所以就用心做了一下。
算法題：一個任意的三位數(個十百位均不相同)， 求將個十百重新按不同的順序組合共有多少個不同的三位數？分別是什麼？(C#) 示例：123：123，132，213，231，312，321。
一開始的想法就是寫3個 循環就能把答案湊出來，不過要是N位數怎麼辦要寫N個循環嗎？所以馬上想到了 使用遞歸來解決問題。每次取一個數字然後再從剩下的數字中拿第一個，然後依 次類推直到拿到最後一個數字結束。不過這有個小問題就是對於1來說有兩個結果 123、132，這需要用List來保存結果不過這樣實在不夠優雅所以我選擇了鐘愛的 yield return來簡化代碼。
對於遞歸程序來說最關鍵的就是找到終結點， 一開始我試了幾個終結條件都不成功，最後冷靜下來琢磨了一下一次排序的過程 就是把N個數都枚舉了一遍所以終結條件就是數字的位數。就省最後一個問題了排 列中不能有重復的，這個只要模擬一下排序的過程就明白了：
開始：選出 最左邊的數字1，其字符串下標為0，當前枚舉了1個數
遞歸第一次：從頭 開始遍歷，因為上一輪下標為0的數字已經被取了，所以使用下標為1的數字，判 斷該下標1是否已經被使用，因為沒被使用，那麼繼續遞歸，當前枚舉了2個數
遞歸第二次：因為當前枚舉的是第3個數所以到達終結點，返回3
在這一次排序過程中我們需要記錄每次被選中的數字的下標，再下次枚舉時要進 行判斷是否已經存在了，所以我使用了一個和數字位數相同大小的數組來記錄每 次排序過程中選中的數字的下標。
好了，上面都沒看懂也沒關系直接上代 碼，代碼是最好的文檔，不過在貼具體代碼之前我要下介紹下我的兩個輔助函數 ：
view plaincopy to clipboardprint?
//將一個操作施加 到每一個遍歷出來的元素上
public static void For<T>(this IEnumerable<T> itor, Action<T> proc)
{
foreach (T item in itor)
proc(item);
}
//判斷一個元素是否在 一個數組中
public static bool Exist<T>(this T[] arr, Func<T, bool> predicate)
{
for (int i = 0; i < arr.Length; ++i)
{
if (predicate(arr[i]))
return true;
}
return false;
}
//ok,核心代碼來了:
public static IEnumerable<string> Combin(string source)
{
int[] trace = new int[source.Length];
for (int i = 0; i < source.Length; ++i)
{
foreach (string item in Combin(source, i, 1, trace))
{
yield return item;
}
}
}
/// <summary>
/// 排序遞歸算法
/// </summary>
/// <param name="source"> 數字</param>
/// <param name="cur"> 當前下標</param>
/// <param name="deep">當前枚舉個數</param>
/// <param name="trace">跟蹤，用於去重復</param>
/// <returns>返回排序好的數字</returns>
private static IEnumerable<string> Combin(string source, int cur, int deep, int[] trace)
{
char tmp = source[cur]; //得到當前枚舉數字
trace[deep - 1] = cur; //將當前下標 放入跟蹤中
if (deep == source.Length) //終結條件
yield return tmp.ToString ();
else
{
for (int i = 0; i < source.Length; ++i) //枚舉
{
for (int j = deep; j < trace.Length; ++j) //跟蹤清零
trace[j] = -1; //-1代表未作記錄
if (cur == i || trace.Exist(p => //重復過濾
{
if (p == -1) return false;
return p == i;
}))
continue;
foreach (string tail in Combin(source, i, deep + 1, trace))
{
yield return tmp + tail;
}
}
}
}
//看看效果吧
public static void Main()
{
Combin("1234").For(i => Console.WriteLine(i));
}
//將一個操作施加到每一個遍歷 出來的元素上
public static void For<T>(this IEnumerable<T> itor, Action<T> proc)
{
foreach (T item in itor)
proc(item);
}
//判斷一個元素是否在一個數組中
public static bool Exist<T>(this T[] arr, Func<T, bool> predicate)
{
for (int i = 0; i < arr.Length; ++i)
{
if (predicate (arr[i]))
return true;
}
return false;
}
//ok,核心 代碼來了:
public static IEnumerable<string> Combin (string source)
{
int[] trace = new int [source.Length];
for (int i = 0; i < source.Length; ++i)
{
foreach (string item in Combin(source, i, 1, trace))
{
yield return item;
}
}
}
/// <summary>
/// 排序遞歸 算法
/// </summary>
/// <param name="source">數字</param>
/// <param name="cur">當前下標</param>
/// <param name="deep">當前枚舉個數</param>
/// <param name="trace">跟蹤，用於去重復 </param>
/// <returns>返回排序好的數字 </returns>
private static IEnumerable<string> Combin(string source, int cur, int deep, int[] trace)
{
char tmp = source[cur]; //得 到當前枚舉數字
trace[deep - 1] = cur; //將當前下標放入跟蹤中
if (deep == source.Length) //終結條件
yield return tmp.ToString();
else
{
for (int i = 0; i < source.Length; ++i) //枚舉
{
for (int j = deep; j < trace.Length; ++j) //跟蹤清零
trace[j] = -1; //-1代表未作記錄
if (cur == i || trace.Exist(p => //重復 過濾
{
if (p == -1) return false;
return p == i;
}))
continue;
foreach (string tail in Combin(source, i, deep + 1, trace))
{
yield return tmp + tail;
}
}
}
}
//看看效果吧
public static void Main()
{
Combin ("1234").For(i => Console.WriteLine(i));
}
還不錯是吧,不過現在只能處理字符串,如果輸入是這樣的" 中國 天津 河北區 志成道" 我該如何處理呢,或者輸入的不是字符串而是一 組對象呢?恩,該到泛型上場了.不知你 發現了沒有所謂處理數字排序問題其實可 以泛化到處理對一個數組排序問題,"1234"其 實就是一個char數組而 已,所以完全可以替換成其他任何類型.細心的讀者你有沒有感覺 出我使用trace 去重復的優勢呢.呵呵,我不需要讓自定義去繼承IComparer<T>接口同時 這 個效率也非常高.不過因為是泛型的所以我沒法確定我的返回來行了,因為對於 char[] 來說可以返回string,其他的類型就不好說了,所以我干脆讓用戶自定義返 回類型這樣更 靈活,比如可以返回"1-3-2-4"這樣的結果.好了下面來 看看通過的泛型版本的組合算法吧：
view plaincopy to clipboardprint?
//這個類只是為了方便創建Combination<T>實例用 的
public class Combination
{
public static Combination<T> New<T>(T[] source)
{
return new Combination<T>(source);
}
}
public class Combination<T>
{
T[] _source;
public Combination(T[] source)
{
this._source = source;
}
public IEnumerable<R> Combin<R>(Func<T, R, R> format)
{
var trace = new int [this._source.Length];
for (var i = 0; i < this._source.Length; ++i)
{
foreach (var item in Combin(i, 1, trace, format))
{
yield return item;
}
}
}
/// <summary>
/// 排序的核心遞歸算法
/// </summary>
/// <typeparam name="R">返回類型 </typeparam>
/// <param name="source">要排序的數據源</param>
/// <param name="cur">當前選擇位置</param>
/// <param name="deep">當前遞歸深度 </param>
/// <param name="trace">跟 蹤，用於去重復</param>
/// <param name="format">輸出格式</param>
/// <returns>格式化後的返回類型</returns>
private IEnumerable<R> Combin<R>(int cur, int deep, int[] trace, Func<T, R, R> format)
{
var tmp = this._source[cur]; //得到當前要排序的項
trace[deep - 1] = cur; //記錄 trace
if (deep == this._source.Length) //判斷遞歸是否結束
yield return format (tmp, default(R)); //返回格式化結果
else
{
for (var i = 0; i < this._source.Length; ++i)
{
for (var j = deep; j < trace.Length; ++j) //對trace進行初始化
trace[j] = -1;
if (cur == i || trace.Exist(p =>{ //去重復
if (p == -1) return false;
return p == i;
}))
continue;
//遞歸執行
foreach (var tail in Combin(i, deep + 1, trace, format))
{
yield return format(tmp, tail); //合並結果並輸出
}
}
}
}
}
//這下就完美了,來個例子是一下吧:
public static void Main9()
{
//查詢時關 鍵詞的多種組合方式
string str = "中國 天津 河北區 志 成道";
Combination.New(str.Split(' ')).Combin<string>((p, r) => p + "-" + r).For(i => Console.WriteLine(i.TrimEnd('-')));
//N位 數排序
string num = "1234";
Combination.New(num.ToCharArray()).Combin<string>((p, r) => p + r).For(i => Console.WriteLine(i));
}
//這個類只 是為了方便創建Combination<T>實例用的
public class Combination
{
public static Combination<T> New<T>(T[] source)
{
return new Combination<T>(source);
}
}
public class Combination<T>
{
T[] _source;
public Combination(T[] source)
{
this._source = source;
}
public IEnumerable<R> Combin<R>(Func<T, R, R> format)
{
var trace = new int[this._source.Length];
for (var i = 0; i < this._source.Length; ++i)
{
foreach (var item in Combin(i, 1, trace, format))
{
yield return item;
}
}
}
/// <summary>
/// 排序的核心遞歸算法
/// </summary>
/// <typeparam name="R">返回類型</typeparam>
/// <param name="source">要排序的數據源</param>
/// <param name="cur">當前選擇位置 </param>
/// <param name="deep">當前 遞歸深度</param>
/// <param name="trace">跟蹤，用於去重復</param>
/// <param name="format">輸出格式</param>
/// <returns>格式化後的返回類型</returns>
private IEnumerable<R> Combin<R>(int cur, int deep, int[] trace, Func<T, R, R> format)
{
var tmp = this._source[cur]; //得到當前要排序 的項
trace[deep - 1] = cur; //記錄trace
if (deep == this._source.Length) //判斷遞歸是否結束
yield return format(tmp, default(R)); //返回格式化結果
else
{
for (var i = 0; i < this._source.Length; ++i)
{
for (var j = deep; j < trace.Length; ++j) //對trace進行初始化
trace[j] = -1;
if (cur == i || trace.Exist(p =>{ //去重復
if (p == -1) return false;
return p == i;
}))
continue;
//遞歸執行
foreach (var tail in Combin(i, deep + 1, trace, format))
{
yield return format(tmp, tail); //合並結果並輸出
}
}
}
}
}
//這下就完美了,來個例子是一下吧:
public static void Main9()
{
//查詢時關鍵詞的多 種組合方式
string str = "中國 天津 河北區 志成道 ";
Combination.New(str.Split(' ')).Combin<string>((p, r) => p + "-" + r).For(i => Console.WriteLine(i.TrimEnd('-')));
//N位 數排序
string num = "1234";
Combination.New(num.ToCharArray()).Combin<string>((p, r) => p + r).For(i => Console.WriteLine(i));
}
我 寫的這個方法可能性能上會有損失(因為使用了yield return)不過我認為它的通 用性才是關鍵,希望有熱心網友能幫我優化代碼.謝謝觀賞!
