TL;DR: как найти многомерную перестановку массивов в php и как оптимизировать для больших массивов?
Это продолжение этого вопроса: как найти многомерную перестановку массива в php
у нас есть script для сортировки массива, идея состоит в том, чтобы найти уникальную перестановку массива, правила для поиска этой перестановки:
- Входной массив содержит множество массивов.
- Каждый внутренний массив содержит уникальные элементы.
- Каждый внутренний массив может иметь разную длину и разные значения.
- Выходной массив должен содержать точные значения.
- Внутренний массив вывода должен иметь уникальные значения на одном и том же ключе.
- Если нет решения, допустимы подстановочные знаки
ie.: null.- Подстановочные знаки можно дублировать на одном и том же ключе.
- Решение должно иметь как можно меньше подстановочных знаков.
- Алгоритм должен иметь возможность обрабатывать массив до 30x30 менее чем за 180 секунд.
У меня есть это решение:
function matrix_is_solved(array $matrix) {
foreach (array_keys(current($matrix)) as $offset) {
$column = array_filter($raw = array_column($matrix, $offset));
if (count($column) != count(array_unique($column))) return false;
}
return true;
}
function matrix_generate_vectors(array $matrix) {
$vectors = [];
$columns = count(current($matrix));
$gen = function ($depth=0, $combo='') use (&$gen, &$vectors, $columns) {
if ($depth < $columns)
for ($i = 0; $i < $columns; $i++)
$gen($depth + 1, $i . $combo);
else
$vectors[] = array_map('intval', str_split($combo));
};
$gen();
return $vectors;
}
function matrix_rotate(array $matrix, array $vector) {
foreach ($matrix as $row => &$values) {
array_rotate($values, $vector[$row]);
}
return $matrix;
}
function matrix_brute_solve(array $matrix) {
matrix_make_square($matrix);
foreach (matrix_generate_vectors($matrix) as $vector) {
$attempt = matrix_rotate($matrix, $vector);
if (matrix_is_solved($attempt))
return matrix_display($attempt);
}
echo 'No solution';
}
function array_rotate(array &$array, $offset) {
foreach (array_slice($array, 0, $offset) as $key => $val) {
unset($array[$key]);
$array[$key] = $val;
}
$array = array_values($array);
}
function matrix_display(array $matrix = null) {
echo "[\n";
foreach ($matrix as $row => $inner) {
echo " $row => ['" . implode("', '", $inner) . "']\n";
}
echo "]\n";
}
function matrix_make_square(array &$matrix) {
$pad = count(array_keys($matrix));
foreach ($matrix as &$row)
$row = array_pad($row, $pad, '');
}
$tests = [
[ ['X'], ['X'] ],
[ ['X'], ['X'], ['X'] ],
[ [ 'X', '' ], [ '', 'X' ] ],
[ ['X', 'Y', 'Z'], ['X', 'Y'], ['X']],
[ ['X', 'Y'], ['X', 'Y'], ['X', 'Y'] ]
];
array_map(function ($matrix) {
matrix_display($matrix);
echo "solved by:" . PHP_EOL;
matrix_brute_solve($matrix);
echo PHP_EOL;
}, $tests);
И это отлично работает на малом массиве, но проблема в том, что это итерация по всем возможностям перемещений массивов, а для массива вроде 6x6 это просто слишком много для вычисления - O(nn) как во времени, так и в пространстве!
