還不錯是吧,不過現在只能處理字符串,如果輸入是這樣的" 中國 天津 河北區 志成道" 我該如何處理呢,或者輸入的不是字符串而是一 組對象呢?恩,該到泛型上場了.不知你 發現了沒有所謂處理數字排序問題其實可 以泛化到處理對一個數組排序問題,"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)不過我認為它的通 用性才是關鍵,希望有熱心網友能幫我優化代碼.謝謝觀賞!
