Мобильная версияTLDR: how to find multidimensional array permutation in php and how to optimize for bigger arrays?
This is continuation of this question: how to find multidimensional array permutation in php
we have script for sorting array, idea is to find unique permutation of array, rules to find this permutation are:
- Input array contains set of arrays.
- Each inner array contains unique elements.
- Each inner array may have different length and different values.
- Output array must contain exact same values.
- Output inner array must have unique values on same key.
- If there is no solution, wildcard ie.: null are allowed.
- Wildcards can be duplicated on same key.
- Solution should have as few wildcards as possible.
- Algorithm should be able to handle array up to 30x30 in less than 180 s.
i have this solution so far:
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); And this works perfectly on small array, but trouble is this iterating over all possibilities of array movements, and for array like 6x6 this is just too much to compute - O(nn) in both time and space!
Источник: https://stackoverflow.com/questions/472 ... ermutation
