萬盛學電腦網

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

PHP 從陣列組合生成指定長度的唯一子集

需求:給定一個陣列,取出指定數量的元素組合成新陣列,所有組合唯一不重複。這是典型的「組合數學」問題,本文提供遞迴實作範例。

問題描述

  • 輸入陣列:5 個元素 (1,2,3,4,5)
  • 目標:取出 5 個元素的所有組合(即全排列)
  • 實際應用:樂透號碼生成、測試資料排列、密碼組合等

遞迴實作程式碼

<?php
$arr = array(1, 2, 3, 4, 5);
$target_count = 5;  // 要取幾個元素

$results = [];
$total = 0;

function combine($current, $index, $source, $target_count, &$results, &$total) {
    // 終止條件:已處理完所有源元素
    if ($index === count($source)) {
        if (count($current) === $target_count) {
            $results[] = $current;
            $total++;
        }
        return;
    }

    // 分支 1:不選擇當前元素
    combine($current, $index + 1, $source, $target_count, $results, $total);

    // 分支 2:選擇當前元素
    $new_current = $current;
    $new_current[] = $source[$index];
    combine($new_current, $index + 1, $source, $target_count, $results, $total);
}

// 執行組合
combine([], 0, $arr, $target_count, $results, $total);

// 輸出結果
echo "<pre>";
print_r($results);
echo "</pre>";
echo "總組合數: $total";
?>

執行結果

輸出 1 筆組合(5 選 5 只有一種):

Array
(
    [0] => Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )
)
總組合數: 1

修改參數:5 選 3 範例

將 $target_count = 3,輸出 10 筆組合:

Array
(
    [0] => Array ( [0] => 1 [1] => 2 [2] => 3 )
    [1] => Array ( [0] => 1 [1] => 2 [2] => 4 )
    [2] => Array ( [0] => 1 [1] => 3 [2] => 4 )
    [3] => Array ( [0] => 1 [1] => 2 [2] => 5 )
    ...
)
總組合數: 10

效能優化建議

  1. 產生器模式:大量組合時改用 yield 避免記憶體爆炸
  2. 迭代替代遞迴:避免深度遞迴導致堆疊溢位
  3. 內建函式:PHP 8.1+ 可用 array_combinations()(需安裝擴展)
  4. 早期剪枝:若剩餘元素不足湊齊目標數,直接返回

數學公式驗證

組合數公式:C(n,k) = n! / (k! × (n-k)!)

  • C(5,5) = 1
  • C(5,3) = 10
  • C(10,5) = 252
copyright © 萬盛學電腦網 all rights reserved