PHP 實現全排列算法：遞歸回溯與字典序兩種核心思路完整代碼

全排列是經典算法問題：從 n 個不同元素中取出所有元素，按順序排列，共 n! 種結果。本文提供兩種 PHP 實現——遞歸回溯（易理解）與字典序迭代（無遞歸、常用於下一個排列），並附帶效能對比與實戰避坑指南。

數學基礎

• 元素集合：['A','B','C','D']（n=4）
• 全排列數：4! = 24
• 輸出示例：ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, ...

方法一：遞歸回溯（標準教學實現）

<?php
function permuteRecursive(array $elements): array {
    $result = [];
    $n = count($elements);
    $used = array_fill(0, $n, false);
    $path = [];

    function backtrack(array &$elements, array &$used, array &$path, array &$result) {
        if (count($path) === count($elements)) {
            $result[] = implode('', $path); // 或保存陣列副本
            return;
        }
        foreach ($elements as $i => $val) {
            if ($used[$i]) continue;
            $used[$i] = true;
            $path[] = $val;
            backtrack($elements, $used, $path, $result);
            array_pop($path);
            $used[$i] = false;
        }
    }
    backtrack($elements, $used, $path, $result);
    return $result;
}

$arr = ['A','B','C','D'];
$perms = permuteRecursive($arr);
echo "總共 " . count($perms) . " 種排列<br>";
foreach ($perms as $p) echo $p . "<br>";

關鍵點：

• $used 陣列標記元素是否已進入當前路徑，避免重複使用。
• $path 存儲當前排列，滿長度時加入結果集。
• 時間複雜度 O(n! * n)，空間複雜度 O(n)（遞歸棧 + 路徑）。

方法二：字典序迭代（非遞歸、STL next_permutation 思想）

核心步驟：

1. 將陣列排序為最小字典序（升序）。
2. 重複：輸出當前排列 → 找到右側第一個升序對 a[i] < a[i+1] → 在右側找到比 a[i] 大的最小元素 a[j] → 交換 a[i] ↔ a[j] → 反轉 i+1 到末尾 → 得到下一排列。
3. 直到無升序對（已達最大字典序）停止。

function permuteNext(array $elements): Generator {
    sort($elements); // 確保起始為最小字典序
    yield implode('', $elements);
    while (true) {
        $n = count($elements);
        // 1. 從右向左找第一個 a[i] < a[i+1]
        $i = $n - 2;
        while ($i >= 0 && $elements[$i] >= $elements[$i+1]) $i--;
        if ($i < 0) break; // 已是最大排列
        // 2. 從右向左找第一個 a[j] > a[i]
        $j = $n - 1;
        while ($elements[$j] <= $elements[$i]) $j--;
        // 3. 交換
        [$elements[$i], $elements[$j]] = [$elements[$j], $elements[$i]];
        // 4. 反轉 i+1 到末尾
        $left = $i + 1;
        $right = $n - 1;
        while ($left < $right) {
            [$elements[$left], $elements[$right]] = [$elements[$right], $elements[$left]];
            $left++; $right--;
        }
        yield implode('', $elements);
    }
}

// 使用 Generator 惰性輸出，記憶體 O(1)
foreach (permuteNext(['A','B','C','D']) as $p) {
    echo $p . "<br>";
}

優勢：

• 無遞歸棧溢出風險（n 較大時）。
• Generator 惰性生成，記憶體常數級。
• 易於實現「求第 k 個排列」、「求下一個排列」等變體。

效能對比（n=8，40320 排列）

結論：生產環境推薦字典序 + Generator，既快又省記憶體。

實戰變體：去重全排列（元素含重複值）

function permuteUnique(array $nums): array {
    sort($nums);
    $result = [];
    $used = array_fill(0, count($nums), false);
    $path = [];
    function backtrackUnique(array &$nums, array &$used, array &$path, array &$result) {
        if (count($path) === count($nums)) {
            $result[] = $path;
            return;
        }
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i]) continue;
            // 剪枝：同層級相同值跳過
            if ($i > 0 && $nums[$i] === $nums[$i-1] && !$used[$i-1]) continue;
            $used[$i] = true;
            $path[] = $nums[$i];
            backtrackUnique($nums, $used, $path, $result);
            array_pop($path);
            $used[$i] = false;
        }
    }
    backtrackUnique($nums, $used, $path, $result);
    return $result;
}
// 輸入 [1,1,2] → [[1,1,2],[1,2,1],[2,1,1]]

總結

全排列算法核心在於「有序選擇 + 狀態回溯」。PHP 中：

• 教學/小規模（n ≤ 8） → 遞歸回溯代碼最直觀。
• 生產/大規模/串流處理 → 字典序迭代 + Generator。
• 含重複元素 → 排序 + 同層剪枝（$i>0 && $a[$i]===$a[$i-1] && !$used[$i-1]）。

掌握兩種核心模板，即可應對面試與實際業務中的所有排列組合變體。