您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

PHP排列組合算法實現與性能深度對比

編輯：PHP 相關知識

在PHP開發中，排列組合是常見的算法需求。本文將深入探討兩種實現組合算法的方法，並通過實際測試對比它們的性能表現，幫助開發者選擇最優方案。

需求背景

目標是從一個包含18個元素的數組中，找出所有長度為6的不重複組合。這是一個典型的組合數學問題，對應公式 C(18,6) = 18,564 種可能結果。

方法一：遞歸字符串拼接法

該方法採用經典的遞歸思想：每次遞歸處理第一個元素，分為「包含該元素」和「不包含該元素」兩種情況，最後通過字符串拼接返回結果。

function getCombinationToString($arr, $m) {
    $result = array();
    if ($m == 1) {
        return $arr;
    }
    if ($m == count($arr)) {
        $result[] = implode(',', $arr);
        return $result;
    }
    
    $temp_firstelement = $arr[0];
    unset($arr[0]);
    $arr = array_values($arr);
    
    // 包含第一個元素的組合
    $temp_list1 = getCombinationToString($arr, $m - 1);
    foreach ($temp_list1 as $s) {
        $result[] = $temp_firstelement . ',' . $s;
    }
    unset($temp_list1);
    
    // 不包含第一個元素的組合
    $temp_list2 = getCombinationToString($arr, $m);
    foreach ($temp_list2 as $s) {
        $result[] = $s;
    }
    unset($temp_list2);
    
    return $result;
}

$arr = range(1, 18);
$t = getCombinationToString($arr, 6);
var_dump($t);

測試結果： 執行時間約 238ms，內存佔用較低。

方法二：數組切片遞歸法

此方法使用 array_slice 和 array_merge 操作數組，直接構建結果數組而非字符串，代碼結構更清晰但涉及大量數組複製操作。

function getCombinAryByNum($arr, $num, $t = array()) {
    if ($num == 0) {
        return array($t);
    }
    $r = array();
    for ($i = 0, $l = count($arr); $i <= $l - $num; $i++) {
        $tmp = getCombinAryByNum(
            array_slice($arr, $i + 1), 
            $num - 1, 
            array_merge($t, array($arr[$i]))
        );
        $r = array_merge($r, $tmp);
    }
    return $r;
}

$arr = range(1, 18);
$ss = getCombinAryByNum($arr, 6);
var_dump($ss);

測試結果： 執行時間約 710ms，比方法一慢近3倍。

性能分析與優化建議

指標	方法一(字符串)	方法二(數組)
執行時間	238ms	710ms
內存效率	較高	較低(頻繁數組複製)
代碼可讀性	中等	較好
結果格式	字符串數組	多維數組

核心差異解析

數據結構操作： 方法一僅操作字符串和索引，避免了大量數組複製；方法二頻繁調用 array_slice 和 array_merge，產生大量臨時數組，導致內存分配和垃圾回收開銷巨大。
遞歸深度： 兩者遞歸深度相同，但方法二每層遞歸都創建新數組，內存壓力呈指數級增長。
適用場景： 方法一適合大數據量、高性能要求場景；方法二適合結果需進一步結構化處理、數據量較小的場景。