前兩天看到了這篇帖子：看到的兩道面試題，裡面的第二道題非常有代表性， 所以就用心做了一下。
算法題：一個任意的三位數(個十百位均不相同)， 求將個十百重新按不同的順序組合共有多少個不同的三位數？分別是什麼？(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));
}
