-
N位数排序的通用解决方法
前两天看到了这篇帖子：看到的两道面试题，里面的第二道题非常有代表性，所以就用心做了一下。
算法题： 一个任意的三位数(个十百位均不相同)，求将个十百重新按不同的顺序组合共有多少个不同的三位数？分别是什么？(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)不过我认为它的通用性才是关键,希望有热心网友能帮我优化代码.谢谢观赏!
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));
}
