前两天看到了这篇帖子：看到的两道面试题，里面的第二道题非常有代表性， 所以就用心做了一下。
算法题：一个任意的三位数(个十百位均不相同)， 求将个十百重新按不同的顺序组合共有多少个不同的三位数？分别是什么？(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));
}