PHP
associative arrays
cartesian product
programming
web development

Finding cartesian product with PHP associative arrays

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Introduction

Cartesian products with associative arrays are common in configuration generation, feature matrix testing, and variant pricing. The main risk is explosive growth in result count and memory use. A practical implementation should be clear, deterministic, and able to switch to streaming when combinations become large.

Define Input and Output Contract

Input shape usually looks like keyed arrays of options:

php
1$options = [
2    'size' => ['S', 'M'],
3    'color' => ['black', 'white'],
4    'region' => ['US', 'CA'],
5];

Expected output is an array of associative rows, each containing one value per key.

Iterative Cartesian Product Implementation

A loop-based approach is easy to follow and maintain.

php
1<?php
2function cartesianProduct(array $input): array {
3    $result = [[]];
4
5    foreach ($input as $key => $values) {
6        $next = [];
7
8        foreach ($result as $row) {
9            foreach ($values as $value) {
10                $copy = $row;
11                $copy[$key] = $value;
12                $next[] = $copy;
13            }
14        }
15
16        $result = $next;
17    }
18
19    return $result;
20}
21
22print_r(cartesianProduct($options));

This method is deterministic if source key order is deterministic.

Estimating Result Size Early

Before generating combinations, compute estimated size.

php
1<?php
2function estimateCartesianSize(array $input): int {
3    $size = 1;
4    foreach ($input as $values) {
5        $size *= count($values);
6    }
7    return $size;
8}
9
10echo estimateCartesianSize($options), PHP_EOL;

If estimate is too high, avoid full materialization.

Generator-Based Streaming Alternative

For large spaces, use generators to emit rows one by one.

php
1<?php
2function cartesianGenerator(array $entries, int $i = 0, array $current = []): Generator {
3    if ($i === count($entries)) {
4        yield $current;
5        return;
6    }
7
8    [$key, $values] = $entries[$i];
9    foreach ($values as $value) {
10        $next = $current;
11        $next[$key] = $value;
12        yield from cartesianGenerator($entries, $i + 1, $next);
13    }
14}
15
16$entries = array_map(
17    fn($k, $v) => [$k, $v],
18    array_keys($options),
19    array_values($options)
20);
21
22foreach (cartesianGenerator($entries) as $row) {
23    echo json_encode($row), PHP_EOL;
24}

This keeps memory usage lower and supports early termination.

Pruning Invalid Combinations

In real systems, many combinations are invalid. Prune early instead of filtering the final full output.

For example, skip invalid pairs while generating, not after storing all rows. Early pruning gives major performance gains when constraints are strict.

Practical Use in Web Applications

Common production patterns:

  • Build variant combinations for product configuration.
  • Generate test cases for form permutations.
  • Expand deployment matrix from environment options.

For web endpoints, cap maximum generated rows and return clear error when limits are exceeded to protect server resources.

Testing Recommendations

Example Size Guard

Before generating combinations in web requests, enforce a hard upper limit.

php
1$estimated = estimateCartesianSize($options);
2if ($estimated > 50000) {
3    throw new RuntimeException("Combination space too large");
4}

This simple check prevents memory spikes and keeps API latency predictable when users submit high-cardinality option sets.Test with:

  • Empty option map.
  • Single-key options.
  • Keys with one value each.
  • Constraint-pruned paths.

Also verify output key order if downstream consumers depend on deterministic serialization.

Preserving Deterministic Key Order

If output rows feed snapshot tests, keep associative key order stable before encoding. A simple ksort on each row can make serialized output deterministic across environments and reduce flaky test diffs.

php
foreach ($rows as &$row) { ksort($row); }

Apply this only when canonical ordering is required by consumers.## Common Pitfalls

  • Overwriting partial rows instead of expanding from all current rows.
  • Ignoring exponential growth and crashing memory.
  • Filtering invalid combinations only after full generation.
  • Assuming key iteration order is stable across environments.
  • Returning massive payloads without response size limits.

Summary

  • Cartesian product generation is straightforward but grows quickly.
  • Loop-based expansion is clear for moderate input sizes.
  • Generator-based approach is safer for large combination spaces.
  • Estimate size and apply pruning before heavy processing.
  • Enforce operational limits when exposing results through APIs.

Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

All Rights Reserved.