PHP 實現陣列全排列與所有組合生成算法

全排列是將陣列所有元素按順序重新排列的所有可能情況。本文介紹基於字典序的非遞歸全排列算法，並延伸至組合生成，適用於排列組合驗證、密碼破解測試、遊戲算法等場景。

字典序全排列算法 (非遞歸)

<?php
$source = ['pll', '我', '愛', '你', '嘿'];
sort($source); // 必須從有序序列開始

$last = count($source) - 1;
$x = $last;
$count = 1;

echo implode(',', $source), "<br>"; // 第一種組合

while (true) {
    $y = $x--;
    
    // 1. 從右向左找第一個升序對 (a[x] < a[y])
    if ($source[$x] < $source[$y]) {
        // 2. 從右向左找第一個大於 a[x] 的元素 a[z]
        $z = $last;
        while ($source[$x] > $source[$z]) {
            $z--;
        }
        
        // 3. 交換 a[x] 和 a[z]
        [$source[$x], $source[$z]] = [$source[$z], $source[$x]];
        
        // 4. 將 y 之後的序列逆序 (變為最小排列)
        for ($i = $last; $i > $y; $i--, $y++) {
            [$source[$i], $source[$y]] = [$source[$y], $source[$i]];
        }
        
        echo implode(',', $source), "<br>";
        $x = $last;
        $count++;
    }
    
    if ($x == 0) break; // 已經是最後一個排列
}

echo "Total: $count\n"; // 5! = 120
?>

算法步驟圖解 (以 1,2,3 為例)

初始: 1 2 3
步驟1: 找升序對 (2<3) → x=1, y=2
步驟2: 找大於1的最右元素 → 3 (z=2)
步驟3: 交換 → 1 3 2
步驟4: y後逆序 (無需) → 1 3 2

下一輪: 1 3 2
找升序對 (1<3) → x=0, y=1
找大於1的最右 → 2 (z=2)
交換 → 2 3 1
y後逆序 (3,1→1,3) → 2 1 3

... 直到 3 2 1 結束

遞歸版全排列 (教學對比)

<?php
function permuteRecursive($arr, $start = 0, &$result = []) {
    if ($start >= count($arr) - 1) {
        $result[] = $arr;
        return;
    }
    for ($i = $start; $i < count($arr); $i++) {
        [$arr[$start], $arr[$i]] = [$arr[$i], $arr[$start]];
        permuteRecursive($arr, $start + 1, $result);
        [$arr[$start], $arr[$i]] = [$arr[$i], $arr[$start]]; // 回溯
    }
    return $result;
}

$perms = permuteRecursive([1,2,3]);
print_r($perms);
?>

組合生成 (從 n 個元素中取 k 個)

<?php
/**
 * 生成所有 C(n,k) 組合
 * @param array $elements 元素陣列
 * @param int $k 取幾個
 * @return array 組合陣列
 */
function combinations($elements, $k) {
    $result = [];
    $n = count($elements);
    if ($k > $n) return $result;
    
    // 初始化索引陣列 [0,1,2,...,k-1]
    $indices = range(0, $k - 1);
    
    while (true) {
        // 記錄當前組合
        $combo = [];
        foreach ($indices as $idx) $combo[] = $elements[$idx];
        $result[] = $combo;
        
        // 找到可以遞增的位置
        $i = $k - 1;
        while ($i >= 0 && $indices[$i] == $n - $k + $i) {
            $i--;
        }
        if ($i < 0) break; // 所有組合生成完畢
        
        // 遞增並重置後續位置
        $indices[$i]++;
        for ($j = $i + 1; $j < $k; $j++) {
            $indices[$j] = $indices[$j - 1] + 1;
        }
    }
    return $result;
}

// 測試: 從 [A,B,C,D] 取 2 個
print_r(combinations(['A','B','C','D'], 2));
/*
輸出:
[0] => [A,B]
[1] => [A,C]
[2] => [A,D]
[3] => [B,C]
[4] => [B,D]
[5] => [C,D]
*/
?>

性能與記憶體對比

生成器版全排列 (推薦大數據量)

<?php
function permuteGenerator($arr) {
    $c = count($arr);
    if ($c <= 1) { yield $arr; return; }
    
    // 使用索引排列避免數組複製
    $indices = range(0, $c - 1);
    $cycles = array_reverse(range(1, $c));
    
    yield array_map(fn($i) => $arr[$i], $indices);
    
    while (true) {
        for ($i = $c - 1; $i >= 0; $i--) {
            $cycles[$i]--;
            if ($cycles[$i] == 0) {
                // 循環結束，旋轉索引
                $temp = array_slice($indices, $i);
                array_splice($indices, $i, 1);
                $indices = array_merge($indices, $temp);
                $cycles[$i] = $c - $i;
            } else {
                $j = $cycles[$i];
                [$indices[$i], $indices[$c - $j]] = [$indices[$c - $j], $indices[$i]];
                yield array_map(fn($i) => $arr[$i], $indices);
                break;
            }
        }
        if ($i < 0) return; // 結束
    }
}

// 使用: 逐個處理不佔內存
foreach (permuteGenerator([1,2,3,4,5]) as $perm) {
    // process $perm
}
?>

相關專題推薦

更多算法實現，請參考：《PHP 數據結構與算法教程》、《PHP 程序設計算法總結》、《PHP 組合數學應用》等專題。