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

PHP 實現笛卡爾積排列組合算法：多維陣列全組合生成

編輯：PHP 綜合知識

面對「從每個班級選 1 名學生組成小組」這類問題，本質是求多個集合的笛卡爾積。本文提供高效、無遞歸的 PHP 實現，支援任意維度、任意大小的輸入陣列，並分析時間空間複雜度與優化方向。

問題數學建模

輸入：$n$ 個集合 $S_1, S_2, ..., S_n$，$|S_i| = k_i$
輸出：所有有序元組 $(x_1, x_2, ..., x_n)$，其中 $x_i \in S_i$
總組合數：$N = \prod_{i=1}^n k_i$

迭代算法實現 (O(N) 時間, O(N) 空間)

<?php
/**
 * 計算多維陣列的笛卡爾積
 * @param array $sets 索引陣列 [集合1, 集合2, ...] 或 關聯陣列 ['key' => 集合]
 * @param bool $preserveKeys 是否保留關聯鍵名
 * @return array 組合陣列 [索引 => [鍵=>值...]]
 */
function cartesianProduct(array $sets, bool $preserveKeys = true): array {
    // 過濾空集合
    $sets = array_filter($sets, fn($s) => is_array($s) && !empty($s));
    if (empty($sets)) return [];
    
    // 統一為索引陣列，記錄鍵名
    $keys = [];
    $values = [];
    foreach ($sets as $k => $v) {
        $keys[] = $preserveKeys ? $k : null;
        $values[] = array_values($v); // 重建索引
    }
    $dim = count($values);
    
    // 計算各維度步長
    $strides = [];
    $stride = 1;
    for ($i = $dim - 1; $i >= 0; $i--) {
        $strides[$i] = $stride;
        $stride *= count($values[$i]);
    }
    $total = $stride;
    
    $result = [];
    for ($n = 0; $n < $total; $n++) {
        $combo = [];
        $remaining = $n;
        for ($i = 0; $i < $dim; $i++) {
            $idx = (int)($remaining / $strides[$i]);
            $remaining %= $strides[$i];
            $key = $keys[$i] ?? $i;
            $combo[$key] = $values[$i][$idx];
        }
        $result[] = $combo;
    }
    return $result;
}

// ==================== 使用示例 ====================

// 班級學生數據
$classes = [
    'class_1' => ['Student10', 'Student11'],
    'class_2' => ['Student20', 'Student21', 'Student22'],
    'class_3' => ['Student30'],
    'class_4' => ['Student40', 'Student41', 'Student42', 'Student43'],
];

$groups = cartesianProduct($classes);
echo "總組合數: " . count($groups) . " (預期 2*3*1*4=24)\n";

// 輸出前 5 組
foreach (array_slice($groups, 0, 5) as $i => $group) {
    echo "Group $i: " . implode(', ', $group) . "\n";
}

/*
總組合數: 24
Group 0: Student10, Student20, Student30, Student40
Group 1: Student10, Student20, Student30, Student41
Group 2: Student10, Student20, Student30, Student42
Group 3: Student10, Student20, Student30, Student43
Group 4: Student10, Student21, Student30, Student40
*/

生成器版本 (記憶體友好，適合大數據)

<?php
/**
 * 笛卡爾積生成器：逐個產出組合，不佔用結果陣列記憶體
 */
function cartesianProductGenerator(array $sets): Generator {
    $sets = array_filter($sets, fn($s) => is_array($s) && !empty($s));
    if (empty($sets)) return;
    
    $keys = array_keys($sets);
    $values = array_map('array_values', $sets);
    $dim = count($values);
    
    $strides = [];
    $stride = 1;
    for ($i = $dim - 1; $i >= 0; $i--) {
        $strides[$i] = $stride;
        $stride *= count($values[$i]);
    }
    $total = $stride;
    
    for ($n = 0; $n < $total; $n++) {
        $combo = [];
        $remaining = $n;
        for ($i = 0; $i < $dim; $i++) {
            $idx = (int)($remaining / $strides[$i]);
            $remaining %= $strides[$i];
            $combo[$keys[$i]] = $values[$i][$idx];
        }
        yield $combo;
    }
}

// 使用：逐個處理，無需載入全部到記憶體
foreach (cartesianProductGenerator($classes) as $idx => $group) {
    // 處理單個組合...
    if ($idx > 10000) break; // 可隨時中斷
}

遞歸實現 (教學參考，不推薦生產用)

<?php
function cartesianRecursive(array $sets, int $depth = 0, array $current = []): array {
    if ($depth >= count($sets)) {
        return [$current];
    }
    $key = array_keys($sets)[$depth];
    $result = [];
    foreach ($sets[$key] as $value) {
        $result = array_merge($result, cartesianRecursive($sets, $depth + 1, $current + [$key => $value]));
    }
    return $result;
}

性能對比與複雜度分析

實現	時間複雜度	空間複雜度	優點	缺點
迭代 (索引計算)	O(N × d)	O(N × d)	無遞歸棧溢出風險、速度快、可預分配	需預先計算總數
生成器	O(N × d)	O(d)	常數記憶體、可中斷、流式處理	無法隨機訪問、不可重複迭代
遞歸	O(N × d)	O(N × d + d)	代碼直觀	深度受限、記憶體峰值高、PHP 函數調用開銷大