Поиск декартового произведения с помощью ассоциативных массивов 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 ответов
Вот решение, которое мне не стыдно показать.
обоснование
Предположим, что у нас есть входной массив $input с N подмассивы, как в вашем примере. Каждый вложенный массив имеет Cn предметы, где n это его индекс внутри $input и его ключ Kn, Я буду ссылаться на i й пункт n th-массив как 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,
4а) Для каждого массива внутри $product:
4б) Для каждого значения в наборе VN,2 ... VN,CN, добавить к $product копия $item, но измените значение с помощью ключа KN в VN,m (для всех 2 <= m <= CN).
Две итерации 4а (более $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) {
$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 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[];
}
В 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;
}
Вот что я мог придумать:
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;
}
Если потребление памяти важно или вам не нужны все комбинации, вы можете использовать итератор для генерации одной комбинации за раз. Если вам нужны все комбинации, которые вы можете использовать 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 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) )
{
....
}
И прочитайте это:
Один алгоритм заключается в расширении на каждом шаге предыдущих результатов элементами текущего шага:
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;
}
Это решение использует память для хранения всех комбинаций, а затем возвращает их все сразу. Итак, это быстро, но для этого нужно много памяти. Также рекурсивные функции не используются.