Поиск декартова произведения с помощью ассоциативных массивов PHP
Скажите, что у меня есть массив, подобный следующему:
Array
(
[arm] => Array
(
[0] => A
[1] => B
[2] => C
)
[gender] => Array
(
[0] => Female
[1] => Male
)
[location] => Array
(
[0] => Vancouver
[1] => Calgary
)
)
Как я могу найти декартово произведение, сохраняя ключи внешнего ассоциативного массива и используя их во внутренних? Результат алгоритма должен быть таким:
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.
Я просмотрел довольно много алгоритмов декартового произведения, но я застрял на особенностях сохранения ассоциативных ключей. Текущий алгоритм, который я использую, дает только числовые индексы:
$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);
Любая помощь был бы признателен.
10 answers
Вот решение, которое я не постеснялся бы показать.
Обоснование
Предположим, что у нас есть входной массив $input с N вложенными массивами, как в вашем примере. Каждый
вложенный массив содержит элементы Cn, где n - его индекс внутри $input, а его ключ - Kn. Я буду ссылаться на i-й элемент n-го подмассива как Vn,i.
Можно доказать, что приведенный ниже алгоритм работает (за исключением ошибок) путем индукции:
1) Для N=1 декартово произведение просто array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) -- Всего С1 предметов. Это можно сделать с помощью простого foreach.
2) Предположим, что $result уже содержит декартово произведение первых N-1 подмассивов. Декартово произведение $result и N-го подмассива может быть получено следующим образом:
3) В каждом элементе (массиве) внутри $product добавьте значение KN => VN,1. Запомните полученный элемент (с добавленной стоимостью); Я буду ссылаться на него как $item.
4a) Для каждого массива внутри $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));
Увидеть это в действии!
Вот оптимизированная версия декартовой функции @Джона:
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;
}
Подробнее о математике, лежащей в основе этого алгоритма: http://en.wikipedia.org/wiki/Cartesian_product
Смотрите больше примеров этого алгоритма на разных языках: https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists
Вот что я мог бы придумать:
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
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));
В PHP 7 ответ @Serg может быть сокращен до:
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;
}
Я быстро немного скорректировал ваш код, моя попытка, я думаю, грубая, но посмотрите, работает ли это так, как вы хотите:
$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);
Это решение очень и очень быстрое, если вам нужно всего несколько комбинаций.
Кроме того, потребление памяти очень низкое (он использует плоский array для хранения некоторых integers).
Примечание: рекурсивные функции не используются.
Один алгоритм состоит в том, чтобы на каждом шаге расширять предыдущие результаты с помощью элементов текущего шага:
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;
}
Это решение использует память для хранения всех комбинаций, а затем возвращает их все сразу. Итак, это быстро, но для этого требуется много памяти. Кроме того, рекурсивные функции не используются.