PHP 組合算法實現：從 N 個元素中任意選取的組合總數

數學原理

從 N 個元素中任意選取（至少 1 個）的組合總數 = 2^N - 1（每個元素選/不選，排除全不選）。

若需分類統計每種選取個數的組合數：

• 選 1 個：C(N,1) = N
• 選 2 個：C(N,2) = N(N-1)/2
• ...
• 選 k 個：C(N,k)
• 總和 = Σ C(N,k) = 2^N - 1

遞歸生成所有組合（返回二維數組）

<?php
function combinations(array $elements): array {
    $result = [];
    $n = count($elements);
    // 位掩碼法：1 到 2^n-1
    for ($mask = 1; $mask < (1 << $n); $mask++) {
        $combo = [];
        for ($i = 0; $i < $n; $i++) {
            if ($mask & (1 << $i)) {
                $combo[] = $elements[$i];
            }
        }
        $result[] = $combo;
    }
    return $result;
}

// 使用
$arr = [1, 2, 3, 4, 5];
$combos = combinations($arr);
echo "總組合數: " . count($combos); // 31 = 2^5 - 1
print_r($combos);

迭代器版（記憶體友好，適合大 N）

class CombinationIterator implements Iterator {
    private array $elements;
    private int $n;
    private int $mask = 1; // 從 1 開始，跳過空集
    public function __construct(array $elements) {
        $this->elements = array_values($elements);
        $this->n = count($this->elements);
    }
    public function current(): array {
        $combo = [];
        for ($i = 0; $i < $this->n; $i++) {
            if ($this->mask & (1 << $i)) $combo[] = $this->elements[$i];
        }
        return $combo;
    }
    public function next(): void { $this->mask++; }
    public function key(): int { return $this->mask; }
    public function valid(): bool { return $this->mask < (1 << $this->n); }
    public function rewind(): void { $this->mask = 1; }
}

// 使用
foreach (new CombinationIterator(['A','B','C','D']) as $combo) {
    echo implode(',', $combo) . "\n";
}
// 輸出 15 行組合

應用場景

• 權限矩陣：用戶擁有權限子集的所有組合預計算。
• 測試用例生成：參數組合測試（Pairwise 更高效）。
• 遊戲道具合成配方：材料組合遍歷。
• 特徵工程：特徵子集搜索（配合評分函數剪枝）。

性能提示

• N > 20 時組合數超百萬，記憶體/時間不可接受，需啟發式搜索（遺傳算法、貪心、貝葉斯優化）。
• 僅需總數用 (1 << $n) - 1 直接計算，O(1)。
• 需固定選 k 個用 C(N,k) 組合生成器（遞歸/迭代），避免全量生成再過濾。