# PHP如何實現數組的笛卡爾積
## 什么是笛卡爾積
笛卡爾積（Cartesian Product）是數學中的一個概念，指兩個集合X和Y的笛卡爾積，表示為X × Y，是所有可能的有序對組成的集合。在編程中，這個概念被擴展到多個數組的組合，即給定若干個數組，生成它們所有可能的組合。
例如：
- 數組A = [1, 2]
- 數組B = ['a', 'b']
它們的笛卡爾積結果為：
[
[1, 'a'],
[1, 'b'],
[2, 'a'],
[2, 'b']
]
## PHP實現笛卡爾積的常見方法
### 方法一：遞歸實現
```php
function cartesianProductRecursive(array $arrays): array
{
$result = [];
$current = array_shift($arrays);
if (empty($arrays)) {
foreach ($current as $item) {
$result[] = [$item];
}
return $result;
}
$subResult = cartesianProductRecursive($arrays);
foreach ($current as $item) {
foreach ($subResult as $subItem) {
array_unshift($subItem, $item);
$result[] = $subItem;
}
}
return $result;
}
// 使用示例
$arrays = [
[1, 2],
['a', 'b'],
['x', 'y']
];
print_r(cartesianProductRecursive($arrays));
實現原理： 1. 取出第一個數組作為當前處理數組 2. 遞歸處理剩余數組 3. 將當前數組元素與遞歸結果組合
優缺點： - 優點：代碼簡潔，易于理解 - 缺點：遞歸深度受限于PHP的調用棧，大數據量可能導致棧溢出
function cartesianProductIterative(array $arrays): array
{
$result = [[]];
foreach ($arrays as $currentArray) {
$temp = [];
foreach ($result as $product) {
foreach ($currentArray as $item) {
$temp[] = array_merge($product, [$item]);
}
}
$result = $temp;
}
return $result;
}
// 使用示例
$arrays = [
['紅色', '藍色'],
['S', 'M', 'L'],
['棉質', '滌綸']
];
print_r(cartesianProductIterative($arrays));
實現原理： 1. 初始化結果為一個包含空數組的數組 2. 遍歷每個輸入數組 3. 將當前數組的每個元素與已有結果組合
優缺點： - 優點：不受遞歸深度限制，適合大數據量 - 缺點：內存消耗較大，因為需要保存中間結果
function cartesianProductGenerator(array $arrays): Generator
{
if (empty($arrays)) {
yield [];
return;
}
$first = array_shift($arrays);
foreach ($first as $item) {
foreach (cartesianProductGenerator($arrays) as $rest) {
yield array_merge([$item], $rest);
}
}
}
// 使用示例
$arrays = [
[1, 2, 3],
['a', 'b']
];
foreach (cartesianProductGenerator($arrays) as $combination) {
print_r($combination);
}
實現原理： 1. 使用生成器(yield)逐步產生結果 2. 不需要一次性存儲所有組合
優缺點： - 優點：極大節省內存，適合超大數據集 - 缺點：不能隨機訪問結果，必須順序處理
我們通過一個基準測試比較三種方法的性能（PHP 8.1）：
$testData = [
range(1, 5),
range('a', 'e'),
range('A', 'E')
];
// 遞歸方法
$start = microtime(true);
$resultRecursive = cartesianProductRecursive($testData);
echo "遞歸方法: ".(microtime(true) - $start)."秒\n";
// 迭代方法
$start = microtime(true);
$resultIterative = cartesianProductIterative($testData);
echo "迭代方法: ".(microtime(true) - $start)."秒\n";
// 生成器方法
$start = microtime(true);
$count = 0;
foreach (cartesianProductGenerator($testData) as $_) {
$count++;
}
echo "生成器方法: ".(microtime(true) - $start)."秒 (計數: $count)\n";
典型結果： - 小數據集(5x5x5=125組合)： - 遞歸：0.0003秒 - 迭代：0.0002秒 - 生成器：0.0004秒
結論： - 迭代方法通常最快 - 生成器雖然稍慢但內存效率最高 - 遞歸方法在小數據量時表現良好
$colors = ['紅色', '黑色', '金色'];
$sizes = ['S', 'M', 'L', 'XL'];
$materials = ['棉', '滌綸', '絲綢'];
$variants = cartesianProductIterative([$colors, $sizes, $materials]);
foreach ($variants as $variant) {
echo implode('-', $variant)."\n";
}
$searchParams = [
'price' => ['<100', '100-500', '>500'],
'brand' => ['A', 'B', 'C'],
'rating' => ['4+', '3+']
];
$searchCombinations = cartesianProductRecursive(array_values($searchParams));
$testCases = [
'input' => [null, '', 'test', 123],
'options' => [['strict' => true], ['strict' => false]],
'expected' => [true, false, new Exception()]
];
foreach (cartesianProductGenerator($testCases) as $case) {
// 執行測試...
}
function cartesianProductWithKeys(array $arrays): array
{
$keys = array_keys($arrays);
$values = array_values($arrays);
$product = cartesianProductIterative($values);
return array_map(function($item) use ($keys) {
return array_combine($keys, $item);
}, $product);
}
// 使用示例
$params = [
'color' => ['紅', '藍'],
'size' => [38, 40]
];
print_r(cartesianProductWithKeys($params));
class CartesianProductIterator implements Iterator
{
private $arrays;
private $counters;
private $current;
private $valid;
public function __construct(array $arrays) {
$this->arrays = array_values($arrays);
$this->rewind();
}
public function rewind(): void {
$this->counters = array_fill(0, count($this->arrays), 0);
$this->valid = !empty($this->arrays);
$this->current = $this->generateCurrent();
}
public function current() {
return $this->current;
}
public function key() {
return null;
}
public function next(): void {
for ($i = count($this->arrays) - 1; $i >= 0; $i--) {
$this->counters[$i]++;
if ($this->counters[$i] < count($this->arrays[$i])) {
break;
}
$this->counters[$i] = 0;
if ($i === 0) {
$this->valid = false;
return;
}
}
$this->current = $this->generateCurrent();
}
public function valid(): bool {
return $this->valid;
}
private function generateCurrent() {
$result = [];
foreach ($this->arrays as $i => $array) {
$result[] = $array[$this->counters[$i]];
}
return $result;
}
}
// 使用示例
$iterator = new CartesianProductIterator([
range(1, 1000),
range('a', 'z')
]);
foreach ($iterator as $item) {
// 處理每個組合
}
現象：處理大數組時出現”Allowed memory size exhausted”錯誤
解決方案：
1. 使用生成器版本
2. 增加內存限制：ini_set('memory_limit', '512M');
3. 分批處理數組
現象：不同實現方法產生的組合順序不同
解決方案： 1. 如果需要固定順序，可以在最后對結果排序 2. 統一使用一種實現方法
現象：輸入包含空數組時結果不符合預期
解決方案：
function cartesianProductSafe(array $arrays): array
{
$arrays = array_filter($arrays, function($array) {
return !empty($array);
});
if (empty($arrays)) {
return [];
}
return cartesianProductIterative($arrays);
}
在PHP中實現笛卡爾積有多種方法，各有優缺點： 1. 遞歸實現：代碼簡潔但受限于調用棧深度 2. 迭代實現：性能最好但內存消耗大 3. 生成器實現：內存效率最高但稍慢
選擇哪種方法取決于具體場景： - 小數據集：任意方法均可 - 大數據集：優先考慮生成器 - 需要隨機訪問結果：使用迭代方法
通過本文介紹的各種實現和優化技巧，您可以靈活地在PHP項目中應用笛卡爾積來解決組合問題。 “`
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
