How to Generate the Cartesian Product of an Associative Array While Preserving Keys?

Finding Cartesian Product while Preserving Keys in Associative Arrays

Consider an associative array like the following:

$input = array(
    'arm' => array('A', 'B', 'C'),
    'gender' => array('Female', 'Male'),
    'location' => array('Vancouver', 'Calgary'),
);

The goal is to find the Cartesian product of this array while preserving the original associative keys. The desired output would be:

array(
    [0] => array(
        'arm' => 'A',
        'gender' => 'Female',
        'location' => 'Vancouver'
    ),
    [1] => array(
        'arm' => 'A',
        'gender' => 'Female',
        'location' => 'Calgary'
    ),
    [2] => array(
        'arm' => 'A',
        'gender' => 'Male',
        'location' => 'Vancouver'
    ),
    ...
)

Algorithm Rationale

Assume the input array has N sub-arrays ($input), each with Cn items, where n is its index. The ith item of the nth sub-array is referred to as Vn,i.

The algorithm proves (assuming no bugs) by induction:

1. For N = 1, the Cartesian product is a simple 1D array.

2. Assuming the result already holds the Cartesian product of the first N-1 sub-arrays, it can be extended as follows:

   • Add KN => VN,1 to each item in the current result.
   • For each remaining item in the Nth input sub-array (2 <= m <= CN), add a copy of the item with KN => VN,m.

Code Implementation

function cartesian($input) {
    $result = array();

    while (list($key, $values) = each($input)) {
        if (empty($values)) {
            continue;
        }

        if (empty($result)) {
            foreach ($values as $value) {
                $result[] = array($key => $value);
            }
        } else {
            $append = array();

            foreach ($result as &$product) {
                $product[$key] = array_shift($values);
                $copy = $product;

                foreach ($values as $item) {
                    $copy[$key] = $item;
                    $append[] = $copy;
                }

                array_unshift($values, $product[$key]);
            }

            $result = array_merge($result, $append);
        }
    }

    return $result;
}

Usage

$output = cartesian($input);
print_r($output);

This code will output the desired Cartesian product while preserving the original associative keys.

The above is the detailed content of How to Generate the Cartesian Product of an Associative Array While Preserving Keys?. For more information, please follow other related articles on the PHP Chinese website!