Поиск декартова продукта с ассоциативными массивами PHP

Вот решение, которое мне не стыдно было бы показать.

обоснование

Предположим, что у нас есть входной массив $input с N подмассивами, как в вашем примере. Каждый субмассив имеет элементы Cn , где n – его индекс внутри $input , а его ключ – Kn . Я буду ссылаться на i й элемент n го подматрица как Vn,i .

Можно доказать, что алгоритм, приведенный ниже, может работать (запрещая ошибки) по индукции:

1) Для N = 1 декартово произведение представляет собой просто array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) – всего элементов C1 , Это можно сделать с помощью простого foreach .

2) Предположим, что $result уже содержит декартово произведение первых N-1 подматриц. Декартовой продукт $result и N-й подматрицы можно создать следующим образом:

3) В каждом элементе (массиве) внутри $product добавьте значение KN => VN,1 . Помните полученный результат (с добавленной стоимостью); Я буду называть его как $item .

4а) Для каждого массива внутри $product :

4b) Для каждого значения в наборе VN,2 ... VN,CN , добавьте к $product копию $item , но измените значение с помощью ключа KN на VN,m (для всех 2 <= m <= CN ).

Две итерации 4a (над $product ) и 4b (над N-й входной подматрицей) заканчиваются $result с элементами CN для каждого элемента, который он имел до итераций, поэтому в конце $result действительно содержит декартово произведение первых N вспомогательных массивов.

Поэтому алгоритм будет работать для любого N.

Это было труднее написать, чем следовало бы. Мои формальные доказательства определенно становятся ржавыми …

Код

 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; } 

Применение

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

Смотрите в действии!

Вот оптимизированная версия декартовой функции @ Jon:

 function cartesian($input) { // filter out empty values $input = array_filter($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; } 

И вот математика, стоящая за этим алгоритмом: http://en.wikipedia.org/wiki/Cartesian_product

Вот что я мог придумать:

 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); } 

(Использование псевдо-массива / списка / словарных обозначений ниже, поскольку PHP просто слишком многословен для таких вещей.)

Функция inject преобразует a, [b] в [(a,b)] , то есть она вводит одно значение в каждое значение массива, возвращая массив массивов. Неважно, a или b уже является массивом, он всегда возвращает двухмерный массив.

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

Функция zip применяет функцию inject к каждому элементу массива.

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

Обратите внимание, что это фактически приводит к декартовому продукту, поэтому zip является небольшим неправильным. Простое применение этой функции ко всем элементам в наборе данных дает вам декартово произведение для массива любой длины.

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

Это не содержит ключей, но поскольку элементы все в порядке в результирующем наборе, вы можете просто повторно вставить ключи в результат.

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

Применение этого ко всем элементам в продукте дает желаемый результат.

Вы можете свернуть вышеупомянутые три функции в один длинный оператор, если хотите (что также позволило бы устранить ошибочность).

«Развернутая» версия без анонимных функций для PHP <= 5.2 выглядит следующим образом:

 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; } 

Почему бы не использовать рекурсивный генератор … проблемы с памятью: близко к никому
(и это красиво)

 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[]; } 

Примечание: это не сохраняет ключи; но это начало.

Это должно (не проверено):

 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[]; } 

Другое решение:

 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; } 

Применение:

 $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)); 

Я быстро скорректировал ваш код, моя попытка грубая, я думаю, но посмотрите, работает ли это так, как вы хотите:

 $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); 

Почему бы не использовать базу данных для этого?

Это легко в 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) 

Затем выполните запрос

 $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) ) { .... } 

И прочел это:

Если потребление памяти важно или вам не нужны все комбинации, в конце вы можете использовать итератор для генерации одной комбинации за раз. Если вам нужны все комбинации, вы можете использовать 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; } 

Затем, чтобы получить одно решение за раз, вы можете использовать foreach или next , например:

 $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); 

Это решение очень быстро, если вам нужно всего несколько комбинаций. Кроме того, потребление памяти очень низкое (для хранения некоторых integers используется плоский array ).

Примечание: рекурсивные функции не используются.

В PHP 7 @ Ответ Серга может быть сокращен до:

 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; } 

Один алгоритм состоит в том, чтобы развернуть на каждом шаге предыдущие результаты с текущими шагами:

 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; } 

Это решение использует память для хранения всех комбинаций, а затем возвращает их все сразу. Итак, это быстро, но для этого нужна большая память. Кроме того, рекурсивные функции не используются.