relacion - Encontrar producto cartesiano con matrices asociativas de PHP
prueba de producto cartesiano (10)
Diga que tengo una matriz como la siguiente:
Array
(
[arm] => Array
(
[0] => A
[1] => B
[2] => C
)
[gender] => Array
(
[0] => Female
[1] => Male
)
[location] => Array
(
[0] => Vancouver
[1] => Calgary
)
)
¿Cómo puedo encontrar el producto cartesiano conservando las claves de la matriz asociativa externa y usándolas en las internas? El resultado del algoritmo debería ser este:
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
)
...etc.
He buscado un buen número de algoritmos de productos cartesianos, pero me estoy atascado en los detalles de cómo preservar las claves asociativas. El algoritmo actual que estoy usando solo da índices numéricos:
$result = array();
foreach ($map as $a) {
if (empty($result)) {
$result = $a;
continue;
}
$res = array();
foreach ($result as $r) {
foreach ($a as $v) {
$res[] = array_merge((array)$r, (array)$v);
}
}
$result = $res;
}
print_r($result);
Cualquier ayuda sería apreciada.
¿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 haz 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 leed eso:
¿Por qué no utilizar un generador recursivo ... problemas de memoria: casi ninguno
(y es 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 llaves; pero es un comienzo.
Esto debería 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[];
}
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;
}
Lea más sobre las matemáticas detrás de este algoritmo: http://en.wikipedia.org/wiki/Cartesian_product
Vea más ejemplos de este algoritmo en diferentes idiomas: https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists
Aquí hay una solución de la que no me avergonzaría mostrarla.
Razón fundamental
Supongamos que tenemos una entrada $input input array con N sub-arrays, como en su ejemplo. Cada subarreglo tiene elementos Cn , donde n es su índice dentro de $input , y su clave es Kn . Me referiré al i ésimo elemento de la n ésima sub-matriz como Vn,i .
Se puede probar que el algoritmo siguiente funciona (salvo errores) por inducción:
1) Para N = 1, el producto cartesiano es simplemente una array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) - C1 elementos en total . Esto se puede hacer con un simple foreach .
2) Suponga que $result ya contiene el producto cartesiano de las primeras sub-matrices N-1. El producto cartesiano de $result y la sub-matriz Nth se pueden producir de esta manera:
3) En cada elemento (matriz) dentro de $product , agregue el valor KN => VN,1 . Recuerde el artículo resultante (con el valor agregado); Me referiré a él como $item .
4a) Para cada matriz dentro de $product :
4b) Para cada valor en el conjunto VN,2 ... VN,CN , agregue a $product una copia de $item , pero cambie el valor con la tecla KN a VN,m (para todos 2 <= m <= CN )
Las dos iteraciones 4a (más de $product ) y 4b (sobre la enésima sub-matriz de entrada) terminan con $result con elementos CN para cada artículo que tenía antes de las iteraciones, por lo que al final $result contiene el producto cartesiano del primeras N matrices sub.
Por lo tanto, el algoritmo funcionará para cualquier N.
Esto fue más difícil de escribir de lo que debería haber sido. Mis pruebas formales definitivamente se están oxidando ...
Código
function cartesian($input) {
$result = array();
while (list($key, $values) = each($input)) {
// If a sub-array is empty, it doesn''t affect the cartesian product
if (empty($values)) {
continue;
}
// Seeding the product array with the values from the first sub-array
if (empty($result)) {
foreach($values as $value) {
$result[] = array($key => $value);
}
}
else {
// Second and subsequent input sub-arrays work like this:
// 1. In each existing array inside $product, add an item with
// key == $key and value == first item in input sub-array
// 2. Then, for each remaining item in current input sub-array,
// add a copy of each existing array inside $product with
// key == $key and value == first item of input sub-array
// Store all items to be added to $product here; adding them
// inside the foreach will result in an infinite loop
$append = array();
foreach($result as &$product) {
// Do step 1 above. array_shift is not the most efficient, but
// it allows us to iterate over the rest of the items with a
// simple foreach, making the code short and easy to read.
$product[$key] = array_shift($values);
// $product is by reference (that''s why the key we added above
// will appear in the end result), so make a copy of it here
$copy = $product;
// Do step 2 above.
foreach($values as $item) {
$copy[$key] = $item;
$append[] = $copy;
}
// Undo the side effecst of array_shift
array_unshift($values, $product[$key]);
}
// Out of the foreach, we can add to $results now
$result = array_merge($result, $append);
}
}
return $result;
}
Uso
$input = array(
''arm'' => array(''A'', ''B'', ''C''),
''gender'' => array(''Female'', ''Male''),
''location'' => array(''Vancouver'', ''Calgary''),
);
print_r(cartesian($input));
¡Véalo en acción!
En PHP 7 @ Serg, la respuesta puede acortarse 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;
}
Esto es lo que podría ocurrir:
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 la notación pseudo array / list / dictionary debajo ya que PHP es simplemente demasiado detallado para tales cosas.)
La función de inject transforma a, [b] en [(a,b)] , es decir, inyecta un solo valor en cada valor de una matriz y devuelve 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 de inject a cada elemento de una matriz.
zip([''a'', ''b''], [''foo'', ''bar''])
=> [(''a'', ''foo''), (''a'', ''bar''), (''b'', ''foo''), (''b'', ''bar'')]
Tenga en cuenta que esto realmente produce un producto cartesiano, por lo que zip es un término ligeramente incorrecto. Simplemente al aplicar esta función a todos los elementos en un conjunto de datos en sucesión, obtendrá 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 dado que los elementos están en orden dentro del conjunto de resultados, simplemente puede reinyectar las claves en el resultado.
array_combine([''key1'', ''key2'', ''key3''], [''a'', ''foo'', ''42''])
=> [ key1 : ''a'', key2 : ''foo'', key3 : ''42'' ]
Aplicar esto a todos los elementos en el producto da el resultado deseado.
Puede colapsar las tres funciones anteriores en una única 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 <= 5.2 se vería así:
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;
}
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));
Rápidamente ajusté tu código un poco, creo que mi intento es crudo, 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);
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 necesita todas las combinaciones, puede 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;
}
Luego, 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 necesitas unas pocas combinaciones. Además, el consumo de memoria es muy bajo (utiliza una array plana para almacenar algunos integers ).
Nota: las funciones recursivas no se usan.
Un algoritmo es expandir en cada paso los resultados previos con los elementos de paso actuales:
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. Entonces, es rápido pero necesita mucha memoria. Además, las funciones recursivas no se utilizan.