萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 全排列算法實現:遞歸回溯生成所有排列組合

數學基礎

  • 從 n 個不同元素中取 m 個 (m≤n) 有序排列:P(n,m) = n!/(n-m)!
  • 全排列:m=n,共 n! 種
  • 示例:{A,B,C} 全排列 3! = 6 種

遞歸回溯算法核心思想

  1. 固定第一位,對剩餘元素遞歸全排列
  2. 每輪選擇一個未用元素加入當前排列
  3. 當排列長度 = n 時輸出結果
  4. 回溯:撤銷選擇,嘗試下一個元素

完整實現代碼

<?php
header("Content-Type: text/html; charset=utf-8");

/**
 * 全排列遞歸生成器
 * @param array $remaining 剩餘可選元素
 * @param array $current   當前已構建排列
 * @param array $original  原始元素集合 (用於計算剩餘)
 * @return array 所有排列組成的二維數組
 */
function permute(array $remaining, array $current = [], array $original = null): array {
    if ($original === null) $original = $remaining;
    
    $results = [];
    
    if (count($remaining) > 1) {
        // 保存當前狀態用於回溯
        $snapshot = $current;
        
        foreach ($remaining as $value) {
            // 選擇:加入當前排列
            $current[] = $value;
            
            // 計算新剩餘元素 (集合差集)
            $newRemaining = array_diff($original, $current);
            
            if (count($newRemaining) > 0) {
                // 遞歸
                $results = array_merge($results, permute($newRemaining, $current, $original));
            }
            
            // 回溯:恢復狀態
            $current = $snapshot;
        }
    } elseif (count($remaining) === 1) {
        // 遞歸終點:只剩一個元素,直接構建完整排列
        $current[] = $remaining[0];
        $results[] = implode('', $current);  // 轉字符串或保持數組
    }
    
    return $results;
}

/** 遞歸輸出多維數組 */
function printRecursive(array $arr, int $depth = 0): int {
    $count = 0;
    foreach ($arr as $value) {
        if (is_array($value)) {
            $count += printRecursive($value, $depth + 1);
        } else {
            echo str_repeat('  ', $depth) . $value . "\n";
            $count++;
        }
    }
    return $count;
}

// 測試
$elements = ['A', 'B', 'C', 'D'];
$allPermutations = permute($elements);
echo "共 " . count($allPermutations) . " 種全排列:\n";
printRecursive($allPermutations);

輸出示例 (前 10 行)

ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
...
共 24 種全排列

算法複雜度分析

指標複雜度說明
時間O(n! × n)n! 個排列,每個構建 O(n)
空間O(n! × n)存儲所有結果;遞歸棧 O(n)

⚠️ n ≥ 10 時 n! 爆炸增長 (10! = 3.6M),僅適合小規模集合 (n ≤ 8-9)。大規模需用生成器/迭代器按需產出。

生成器版本 (內存高效)

<?php
function permuteGenerator(array $elements): Generator {
    $n = count($elements);
    $indices = range(0, $n - 1);
    $cycles = array_reverse(range(1, $n));
    
    yield array_map(fn($i) => $elements[$i], $indices);
    
    while (true) {
        for ($i = $n - 1; $i >= 0; $i--) {
            $cycles[$i]--;
            if ($cycles[$i] === 0) {
                // 旋轉
                $temp = $indices[$i];
                array_splice($indices, $i, 1);
                $indices[] = $temp;
                $cycles[$i] = $n - $i;
            } else {
                $j = $cycles[$i];
                // 交換
                [$indices[$i], $indices[$n - $j]] = [$indices[$n - $j], $indices[$i]];
                yield array_map(fn($k) => $elements[$k], $indices);
                break;
            }
        }
        // 檢查是否回到初始狀態
        if ($indices === range(0, $n - 1)) break;
    }
}

// 使用:按需迭代,不佔用巨大內存
foreach (permuteGenerator(['A','B','C','D']) as $perm) {
    echo implode('', $perm) . "\n";
    // 可隨時 break
}

庫函數替代方案

<?php
// 使用 PHP 內置排列 (需安裝 math/combinatorics 或手工實現)
// 簡單場景:array_permutation 非內置,常用組合:
function combinations(array $arr, int $k): Generator {
    $n = count($arr);
    if ($k > $n) return;
    $indices = range(0, $k - 1);
    yield array_map(fn($i) => $arr[$i], $indices);
    while (true) {
        $i = $k - 1;
        while ($i >= 0 && $indices[$i] === $i + $n - $k) $i--;
        if ($i < 0) break;
        $indices[$i]++;
        for ($j = $i + 1; $j < $k; $j++) $indices[$j] = $indices[$j - 1] + 1;
        yield array_map(fn($i) => $arr[$i], $indices);
    }
}

總結

全排列遞歸回溯是經典算法面試題。PHP 實現關鍵點:array_diff 計算剩餘元素、array_merge 合併結果、快照變量實現回溯。生產環境大數據量務必使用 Generator 生成器 逐個產出,避免內存耗盡。理解 array_diff 重建索引特性 (需 array_values 重置) 是避坑關鍵。

copyright © 萬盛學電腦網 all rights reserved