C# N 位數全排列通用解法：泛型遞迴與委派格式化

前言

面試經典題：任意 N 位數字 (或字串、物件陣列) 全排列。本文從字串專用遞迴，進化為**泛型通用解法**：支援任意型別輸入、自定義輸出格式、高效去重、延遲執行 (yield return)。

核心泛型類別

public static class Combination
{
    public static Combination New(T[] source) => new Combination(source);
}

public class Combination
{
    readonly T[] _source;

    public Combination(T[] source) => _source = source;

    // 公開介面：接受格式化委派，回傳 IEnumerable
    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;
    }

    // 遞迴核心
    IEnumerable Combin(int cur, int depth, int[] trace, Func format)
    {
        T current = _source[cur];
        trace[depth - 1] = cur;

        if (depth == _source.Length)
            yield return format(current, default);
        else
        {
            for (int i = 0; i < _source.Length; i++)
            {
                // 初始化 trace 深度之後的位置
                for (int j = depth; j < trace.Length; j++) trace[j] = -1;

                // 去重：當前索引或已在 trace 中
                if (cur == i || trace.Contains(i)) continue;

                foreach (var tail in Combin(i, depth + 1, trace, format))
                    yield return format(current, tail);
            }
        }
    }
}

輔助擴充方法

public static class Extensions
{
    // 對 IEnumerable 每項執行 Action
    public static void For(this IEnumerable src, Action act)
    {
        foreach (var item in src) act(item);
    }

    // 判斷陣列是否存在符合條件元素
    public static bool Contains(this T[] arr, Func pred)
    {
        foreach (var item in arr) if (pred(item)) return true;
        return false;
    }
}

使用範例

// 1. 字串關鍵字組合
string keywords = "中國 天津 河北區 志成道";
Combination.New(keywords.Split(' '))
    .Combin((p, r) => p + "-" + r)
    .For(s => Console.WriteLine(s.TrimEnd('-')));

// 2. N 位數全排列
string digits = "1234";
Combination.New(digits.ToCharArray())
    .Combin((p, r) => p + r)
    .For(s => Console.WriteLine(s));

// 3. 任意物件陣列
var persons = new[] { new { Name = "A" }, new { Name = "B" }, new { Name = "C" } };
Combination.New(persons)
    .Combin((p, r) => p.Name + ">" + r)
    .For(Console.WriteLine);

設計亮點

效能與改進

• yield return 有狀態機開銷，極大 N 可改用迭代器結構體或陣列緩衝。
• trace.Contains 為線性搜尋，可改用 bool[] 或 BitArray 達到 O(1)。
• 輸出型別 R 由呼叫端決定，極大彈性 (字串、StringBuilder、自定義物件)。

結語

從「寫 N 個迴圈」到「泛型遞迴 + 委派格式化」，展現了 C# 泛型、委派、迭代器、擴充方法的組合威力。此模式廣泛適用於組合優化、路徑搜尋、查詢建構等領域。