N 位數全排列算法：從遞歸到泛型通用解決方案的演進

問題背景

給定 N 個不重複元素（如數字 1234），求所有全排列組合。固定 N 可用嵌套循環，但 N 可變時必須用遞歸或迭代算法。

核心遞歸思路

• 維護一個 trace 數組記錄已選元素的索引
• 每層遞歸從剩餘元素中選一個，標記已用
• 遞歸深度達到 N 時輸出一個排列
• 回溯時清除標記，繼續嘗試其他分支

字符串版實現（yield return 流式輸出）

public static IEnumerable Combin(string source)
{
    int[] trace = new int[source.Length];
    for (int i = 0; i < source.Length; i++)
        foreach (var item in Combin(source, i, 1, trace))
            yield return item;
}

private static IEnumerable 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;
            // 去重：當前索引或已用索引跳過
            if (cur == i || trace.Any(p => p != -1 && p == i)) continue;
            foreach (var tail in Combin(source, i, deep + 1, trace))
                yield return tmp + tail;
        }
    }
}

泛型通用版：支持任意類型與自定義輸出格式

public class Combination
{
    private readonly T[] _source;
    public Combination(T[] source) => _source = source;

    public IEnumerable Combin(Func format)
    {
        var trace = new int[_source.Length];
        for (int i = 0; i < _source.Length; i++)
            foreach (var item in Combin(i, 1, trace, format))
                yield return item;
    }

    private IEnumerable Combin(int cur, int deep, int[] trace, Func format)
    {
        var tmp = _source[cur];
        trace[deep - 1] = cur;
        if (deep == _source.Length)
            yield return format(tmp, default(R));
        else
        {
            for (int i = 0; i < _source.Length; i++)
            {
                for (int j = deep; j < trace.Length; j++) trace[j] = -1;
                if (cur == i || trace.Any(p => p != -1 && p == i)) continue;
                foreach (var tail in Combin(i, deep + 1, trace, format))
                    yield return format(tmp, tail);
            }
        }
    }
}

// 輔助工廠
public static class Combination
{
    public static Combination New(T[] source) => new Combination(source);
}

多樣化應用示例

// 數字全排列
Combination.New("1234".ToCharArray())
    .Combin((p, r) => p + r)
    .ForEach(Console.WriteLine);

// 關鍵詞組合（自定義分隔符）
string keywords = "中國 天津 河北區 志成道";
Combination.New(keywords.Split(' '))
    .Combin((p, r) => p + "-" + r)
    .ForEach(s => Console.WriteLine(s.TrimEnd('-')));

擴展方法 ForEach

public static void ForEach(this IEnumerable source, Action action)
{
    foreach (var item in source) action(item);
}

總結

從具體到泛型的演進展示了：

• yield return 實現惰性流式輸出，記憶體友好
• 泛型委托 Func 解耦排列邏輯與輸出格式
• 索引追蹤數組高效去重，無需元素實現 IComparable
• 工廠模式簡化構造調用

適用於關鍵詞組合、測試用例生成、密碼破解字典構建等場景。