C# N 位數全排列基礎實作：字串遞迴與 yield return

前言

面試題：任意三位數 (位數互不相同) 求全排列。本文從朴素三層迴圈出發，引入遞迴解決任意 N 位數，並使用 yield return 簡化結果收集，trace 陣列去重。

遞迴核心邏輯

1. 終止條件：已選擇 N 個數字 (depth == source.Length)。
2. 去重：trace 記錄各深度已用索引，下一層檢查是否重複。
3. 狀態重置：進入新分支前，將 trace[depth...] 設為 -1。

完整程式碼 (字串版)

public static class Permutation
{
    // 擴充方法：執行 Action
    public static void For(this IEnumerable src, Action act)
    {
        foreach (var item in src) act(item);
    }

    // 擴充方法：陣列存在性檢查
    public static bool Exists(this T[] arr, Func pred)
    {
        foreach (var item in arr) if (pred(item)) return true;
        return false;
    }

    // 公開介面
    public static IEnumerable Combin(string source)
    {
        var 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;
    }

    // 遞迴實作
    static IEnumerable Combin(string source, int cur, int depth, int[] trace)
    {
        char current = source[cur];
        trace[depth - 1] = cur;

        if (depth == source.Length)
            yield return current.ToString();
        else
        {
            for (int i = 0; i < source.Length; i++)
            {
                for (int j = depth; j < trace.Length; j++) trace[j] = -1;
                if (cur == i || trace.Exists(idx => idx != -1 && idx == i)) continue;

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

// 使用
Permutation.Combin("1234").For(Console.WriteLine);

關鍵點解析

• yield return：將遞迴轉為迭代器，**不需 List 暫存**，支援無限/大量結果。
• trace 陣列：長度 = N，trace[d] 記錄第 d 層選擇的索引，-1 表示未設定。
• 去重邏輯：cur == i (同層同索引) 或 trace 中已存在 i (上層已用)。
• 狀態重置：每次進入新分支前，將當前深度之後的 trace 清 -1，避免舊殘留干擾。

擴充至泛型 (見下篇)

字串版本固定輸出 string。若需支援 char[]、int[]、任意物件陣列、自定義分隔符，需引入泛型型別參數 T、輸出型別 R、格式化委派 Func —— 這正是第 2 篇 (ID 81426) 的內容。

結語

遞迴 + yield return + trace 去重，優雅解決 N 位全排列。理解終止條件、狀態傳遞、延遲執行三要素，可舉一反三解決組合生成、路徑搜尋、八皇后等回溯問題。