C# 回溯法實作全排列演算法：從 n 取 r 排列完整解析

問題定義

從 `n` 個不同元素 (1~n) 中選取 `r` 個，輸出所有**有序**排列。總數 `P(n,r) = n!/(n-r)!`。

回溯法核心邏輯

• **狀態**：目前已選擇的序列 `a[0..k-1]`。
• **選擇**：下一個位置 `k` 可選的元素 (未被使用、遞增避免重複組合)。
• **約束**：元素不可重複使用；為排列故順序敏感。
• **目標**：`k == r` 時輸出一個解。

遞迴實作 (標準、易懂)

public static class Permutation
{
    public static IEnumerable Generate(int n, int r)
    {
        var a = new int[r];
        var used = new bool[n + 1]; // 1-based
        Backtrack(0);
        yield break; // C# iterator

        void Backtrack(int depth)
        {
            if (depth == r)
            {
                yield return (int[])a.Clone();
                yield break;
            }

            for (int i = 1; i <= n; i++)
            {
                if (!used[i])
                {
                    used[i] = true;
                    a[depth] = i;
                    foreach (var sol in Backtrack(depth + 1)) yield return sol;
                    used[i] = false;
                }
            }
        }
    }
}

// 使用
foreach (var p in Permutation.Generate(4, 2))
    Console.WriteLine(string.Join(" ", p));
// 輸出 12 種: 1 2, 1 3, 1 4, 2 1, 2 3, 2 4, 3 1, 3 2, 3 4, 4 1, 4 2, 4 3

迭代實作 (無遞迴、記憶體友善)

public static IEnumerable GenerateIterative(int n, int r)
{
    var a = new int[r];
    var used = new bool[n + 1];
    int depth = 0;
    a[0] = 1; // 從第一個候選開始

    while (true)
    {
        // 向前嘗試
        while (depth < r)
        {
            // 找下一個可用數字
            int candidate = a[depth];
            while (candidate <= n && used[candidate]) candidate++;
            
            if (candidate <= n)
            {
                a[depth] = candidate;
                used[candidate] = true;
                if (depth + 1 == r)
                {
                    yield return (int[])a.Clone();
                    used[candidate] = false; // 回溯準備下一個
                    continue;
                }
                depth++;
                a[depth] = 1; // 下一層從 1 開始
            }
            else
            {
                // 當層無可用數字，回溯
                break;
            }
        }

        // 回溯
        while (depth >= 0)
        {
            used[a[depth]] = false;
            int next = a[depth] + 1;
            if (next <= n)
            {
                a[depth] = next;
                used[next] = true;
                if (depth + 1 == r)
                {
                    yield return (int[])a.Clone();
                    used[next] = false;
                    continue;
                }
                depth++;
                a[depth] = 1;
                break; // 繼續向前
            }
            depth--;
        }

        if (depth < 0) yield break; // 所有組合窮盡
    }
}

效能與記憶體比較

通用化：任意集合排列

public static IEnumerable Permute(IEnumerable source, int r)
{
    var arr = source.ToArray();
    int n = arr.Length;
    var indices = new int[r];
    var used = new bool[n];
    
    void Backtrack(int d)
    {
        if (d == r)
        {
            yield return indices.Select(i => arr[i]).ToArray();
            return;
        }
        for (int i = 0; i < n; i++)
            if (!used[i])
            {
                used[i] = true; indices[d] = i;
                Backtrack(d + 1);
                used[i] = false;
            }
    }
    Backtrack(0);
}

總結

回溯法是解決排列組合問題的**通用範本**：**狀態 + 選擇 + 約束 + 目標**。遞迴版本最直觀，迭代版本避免堆疊溢位。掌握此模式，可輕鬆擴展至組合、子集、N-Queen、數獨等經典問題。