Encontrar productos cartesianos con arrays asociativos PHP

Aquí está la versión optimizada de la función cartesiana de @Jon:

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

    foreach ($input as $key => $values) {
        $append = array();

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

        $result = $append;
    }

    return $result;
}

Leer más sobre las matemáticas detrás de este algoritmo: http://en.wikipedia.org/wiki/Cartesian_product

Ver más ejemplos de este algoritmo en diferentes idiomas: https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists

Esto es lo que se me ocurrió:{[15]]}

function inject($elem, $array) {
    return array_map(function ($n) use ($elem) { return array_merge((array)$elem, (array)$n); }, $array);
}

function zip($array1, $array2) {
    return array_reduce($array1, function ($v, $n) use ($array2) { return array_merge($v, inject($n, $array2));  }, array());
}

function cartesian_product($array) {
    $keys = array_keys($array);
    $prod = array_shift($array);
    $prod = array_reduce($array, 'zip', $prod);
    return array_map(function ($n) use ($keys) { return array_combine($keys, $n); }, $prod);
}

(Usando pseudo array/list / dictionary notation a continuación ya que PHP es simplemente demasiado detallado para tales cosas.)

La función inject transforma a, [b] en [(a,b)], es decir, inyecta un solo valor en cada valor de una matriz, devolviendo una matriz de matrices. No importa si a o b ya es una matriz, siempre devolverá una matriz bidimensional.

inject('a', ['foo', 'bar'])
    =>  [('a', 'foo'), ('b', 'bar')]

La función zip aplica la función inject función a cada elemento en una matriz.

zip(['a', 'b'], ['foo', 'bar'])
    =>  [('a', 'foo'), ('a', 'bar'), ('b', 'foo'), ('b', 'bar')]

Tenga en cuenta que esto en realidad produce un producto cartesiano, por lo que zip es un ligero nombre incorrecto. Simplemente aplicando esta función a todos los elementos en un conjunto de datos en sucesión le da el producto cartesiano para una matriz de cualquier longitud.

zip(zip(['a', 'b'], ['foo', 'bar']), ['42', '76'])
    =>  [('a', 'foo', '42'), ('a', 'foo', '76'), ('a', 'bar', '42'), …]

Esto no contiene las claves, pero como los elementos están todos en orden dentro del conjunto de resultados, simplemente puede volver a inyectar las claves en el resultado.

array_combine(['key1', 'key2', 'key3'], ['a', 'foo', '42'])
    =>  [ key1 : 'a', key2 : 'foo', key3 : '42' ]

Aplicando esto a todos los elementos en el producto da el resultado deseado.

Puede contraer las tres funciones anteriores en una sola declaración larga si lo desea (lo que también aclararía los nombres incorrectos).

Una versión "desenrollada" sin funciones anónimas para PHP

function inject($elem, $array) {
    $elem = (array)$elem;
    foreach ($array as &$a) {
        $a = array_merge($elem, (array)$a);
    }
    return $array;
}

function zip($array1, $array2) {
    $prod = array();
    foreach ($array1 as $a) {
        $prod = array_merge($prod, inject($a, $array2));
    }
    return $prod;
}

function cartesian_product($array) {
    $keys = array_keys($array);
    $prod = array_shift($array);
    $prod = array_reduce($array, 'zip', $prod);

    foreach ($prod as &$a) {
        $a = array_combine($keys, $a);
    }
    return $prod;
}

¿Por qué no usar un generador recursivo?.. problemas de memoria: cerca de ninguno
(y su hermoso)

function cartesian($a)
{
    if ($a)
    {
        if($u=array_pop($a))
            foreach(cartesian($a)as$p)
                foreach($u as$v)
                    yield $p+[count($p)=>$v];
    }
    else
        yield[];
}

Nota: esto no conserva las claves; pero es un comienzo.

Esto debe hacer (no probado):

function acartesian($a)
{
    if ($a)
    {
        $k=end(array_keys($a));
        if($u=array_pop($a))
            foreach(acartesian($a)as$p)
                foreach($u as$v)
                    yield $p+[$k=>$v];
    }
    else
        yield[];
}

Otra solución:

function getAllVariations($input) {
    $result = array();
    $cnt = array_product(array_map('count', $input));
    $step = 1;
    foreach ($input as $key=>$array) {
        for ($i=0; $i<$cnt; $i++) {
            foreach ($array as $value) {
                for ($k=0; $k<$step; $k++) {
                    $result[$i+$k][$key] = $value;
                }
                $i += $step;
            }
            $i--;
        }
        $step = $step * count($array);
    }
    return $result;
}

Uso:

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

echo "<pre>";
var_dump(getAllVariations($input));

En PHP 7 @ Serg la respuesta se puede acortar a:

function cartesian(array $input)
{
    $result = [[]];
    foreach ($input as $key => $values) {
        $append = [];
        foreach ($values as $value) {
            foreach ($result as $data) {
                $append[] = $data + [$key => $value];
            }
        }
        $result = $append;
    }

    return $result;
}

Ajusté rápidamente tu código un poco, mi intento es crudo, creo, pero mira si esto funciona como quieres:

$result = array();
$nm = '';
foreach ($map as $name => $a) {
    if (empty($result)) {
        $result = $a;
        $nm = $name;
        continue;
    }

    $res = array();
    foreach ($result as $r) {
        foreach ($a as $v) {
            $myr = $r;
            $myv = $v;
            if(!is_array($r)) $myr = array($nm => $r);
            if(!is_array($v)) $myv = array($name => $v);

            $res[] = array_merge($myr, $myv);
        }
    }
    $result = $res;
}
echo "<pre>";
print_r($result);

¿Por qué no usar una base de datos para hacer esto?

Es fácil en MySQL..

table arm
   id integer primary key
   label char

table gender
   id integer primary key
   gender enum('male','female')

table location
   id integer primary key
   city varchar(255)

Luego haga una consulta

$query = mysql_query(" 
  SELECT a.label, g.gender, l.city
  FROM arm a
  CROSS JOIN gender g
  CROSS JOIN location l
  ORDER BY a.id
") or die("Could not execute query");

while($row = mysql_fetch_array($query) )
{
   ....
}

Y léalo en voz alta:

Si el consumo de memoria es importante o no necesita todas las combinaciones al final, podría usar un iterador para generar una combinación a la vez. Si necesitas todas las combinaciones puedes usar iterator_to_array.

function cartezianIterator($inputArray)
{
    $maximumPosition = array_map('count', $inputArray);
    $position = array_pad([], count($inputArray), 0);

    while (false !== ($item = buildItemAtPosition($inputArray, $position))) {

        yield $item;

        $position = incrementPosition($position, $maximumPosition);
    }
}

function buildItemAtPosition($inputArray, $positions)
{
    if ($positions[0] >= count($inputArray[0])) {
        return false;
    }

    $item = [];
    foreach ($inputArray as $rowIndex => $row) {
        $position = $positions[$rowIndex];

        $item[] = $row[$position];
    }

    return $item;
}

function incrementPosition($position, $maximumPosition)
{
    $digitToIncrement = count($position) - 1;

    do {
        $position[$digitToIncrement]++;

        if ($position[$digitToIncrement] < $maximumPosition[$digitToIncrement] || 0 === $digitToIncrement) {
            //no overflow
            break;
        }

        //overflow, reset to zero and increment parent digit
        $position[$digitToIncrement] = 0;

        $digitToIncrement--;
    } while ($digitToIncrement >= 0);

    return $position;
}

Entonces, para obtener una solución a la vez, podría usar un foreach o next, como este:

$iterator = cartezianIterator($inputArray);

//of course, you need to do something with the result...
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);

Esta solución es muy muy rápida si solo necesita unas pocas combinaciones. Además, el consumo de memoria es muy bajo (utiliza un plano array para almacenar algunos integers).

Nota: no se utilizan funciones recursivas.

Un algoritmo es expandir en cada paso los resultados anteriores con los elementos del paso actual:

function cartezian1($inputArray)
{
    $results = [];

    foreach ($inputArray as $group) {
        $results = expandItems($results, $group);
    }

    return $results;
}

function expandItems($sourceItems, $tails)
{
    $result = [];

    if (empty($sourceItems)) {
        foreach ($tails as $tail) {
            $result[] = [$tail];
        }
        return $result;
    }

    foreach ($sourceItems as $sourceItem) {
        foreach ($tails as $tail) {
            $result[] = array_merge($sourceItem, [$tail]);
        }
    }

    return $result;
}

Esta solución usa memoria para almacenar todas las combinaciones y luego las devuelve todas a la vez. Es rápido, pero necesita mucha memoria. Además, no se utilizan funciones recursivas.