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.: nullare 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!
3 Answers
Answers 1
The soluton is quite simple actually. You check the number of unique chars and that's the number of values in the output array. Below code will do what you want almost instantly.
/* HELPERS */ function ShowNice($output) { //nice output: echo '<pre>'; foreach($output as $key=>$val) { echo '<br />' . str_pad($key,2," ",STR_PAD_LEFT) . ' => ['; $first = true; foreach($val as $char) { if (!$first) { echo ', '; } echo "'".$char."'"; $first = false; } echo ']'; } echo '</pre>'; } function TestValid($output, $nullchar) { $keys = count($output[0]); for ($i=0;$i<$keys;$i++) { $found = []; foreach($output as $key=>$val) { $char = $val[$i]; if ($char==$nullchar) { continue; } if (array_key_exists($char, $found)) { return false; //this char was found before } $found[$char] = true; } } return true; } $input = [ 0 => ['X', 'Y', 'Z', 'I', 'J'], 1 => ['X', 'Y', 'Z', 'I'], 2 => ['X', 'Y', 'Z', 'I'], 3 => ['X', 'Y', 'Z', 'I'], 4 => ['X', 'Y', 'Z'], 5 => ['X', 'Y', 'Z'] ]; //generate large table $genLength = 30; //max double alphabet $innerLength = $genLength; $input2 = []; for($i=0;$i<$genLength;$i++) { $inner = []; if (rand(0, 1)==1) { $innerLength--; } for($c=0;$c<$innerLength;$c++) { $ascii = 65 + $c; //upper case if ($ascii>90) { $ascii += 6; //lower case } $inner[] = chr($ascii); } $input2[] = $inner; } //generate large table with different keys $genLength = 10; //max double alphabet $innerLength = $genLength; $input3 = []; for($i=0;$i<$genLength;$i++) { $inner = []; if (rand(0, 1)==1) { //comment o make same length inner arrays, but perhaps more distinct values //$innerLength--; } $nr = 0; for($c=0;$c<$innerLength;$c++) { $ascii = 65 + $c + $nr; //upper case if ($ascii>90) { $ascii += 6; //lower case } $inner[] = chr($ascii); //$inner[] = $c+$nr+1; //increase nr? if (rand(0, 2)==1) { $nr++; } } $input3[] = $inner; } //generate table with numeric values, to show what happens $genLength = 10; //max double alphabet $innerLength = $genLength; $input4 = []; for($i=0;$i<$genLength;$i++) { $inner = []; for($c=0;$c<$innerLength;$c++) { $inner[] = $c+1; } $input4[] = $inner; } $input5 = [ 0 => ['X', 'Y'], 1 => ['X', 'Y'], 2 => ['X', 'Y'], ]; $input6 = [ 0 => ['X', 'Y', 'Z', 'I', 'J'], 1 => ['X', 'Y', 'Z', 'I'], 2 => ['X', 'Y', 'Z', 'I'], 3 => ['X', 'Y', 'Z', 'I'], 4 => ['X', 'Y', 'Z'] ]; /* ACTUAL CODE */ //$input = $input2;//test large table //$input = $input3;//test large unique table //$input = $input4;//test numeric //$input = $input5; //comment $input = $input6; echo '<h2>Input</h2>'; ShowNice($input); //find all distinct chars //find maxlength for any inner array $distinct = []; $maxLength = 0; $minLength = -1; $rowCount = count($input); $flipped = []; $i = 1; foreach($input as $key=>$val) { if ($maxLength<count($val)) { $maxLength = count($val); } if ($minLength>count($val) || $minLength==-1) { $minLength = count($val); } foreach($val as $char) { if (!array_key_exists($char, $distinct)) { $distinct[$char] = $i; $i++; } } $flipped[$key] = array_flip($val); } //keep track of the count for actual chars $actualChars = $i-1; $nullchar = '_'; //add null values to distinct if ($minLength!=$maxLength) { $char = '#'.$i.'#'; $distinct[$nullchar] = $i; //now it only gets add when a key is smaller, not if all are the same size $i++; } //if $distinct count is small then rowcount, we need more distinct $addForRowcount = (count($distinct)<$rowCount); while (count($distinct)<$rowCount) { $char = '#'.$i.'#'; $distinct[$char] = $i; $i++; } //flip the distinct array to make the index the keys $distinct = array_flip($distinct); $keys = count($distinct); //create output $output = []; $start = 0; foreach($input as $key=>$val) { $inner = []; for ($i=1;$i<=$keys;$i++) { $index = $start + $i; if ($index>$keys) { $index -= $keys; } if ($index>$actualChars) { //just add the null char $inner[] = $nullchar; } else { $char = $distinct[$index]; //check if the inner contains the char if (!array_key_exists($char, $flipped[$key])) { $char = $nullchar; } $inner[] = $char; } } $output[] = $inner; $start++; } //UPDATE //at this point there can be a diagonal line with all wildcards. This can be removed to make it one part smaller //this wont happen when we added multiple distinct values because of the rowcount //removing a diagonal line occasionally adds duplicates. //Keep the original and test if the new one is valid. If not, restore the original. $originalOutput = $output; $lastIndex = count($output[0])-1; for($i=$lastIndex;$i>=0;$i--) { if ($output[0][$i]!=$nullchar) { continue;//no wildcard } $found = true; $moveleft=0; foreach($output as $key=>$val){ if ($val[$i-$moveleft]!=$nullchar) { $found = false; break;//if it's not a NULL, we can stop checking } $moveleft++; } if ($found) { //echo 'Found DIA'; //remove extra wildcards $moveleft = 0; foreach($output as $key=>$val){ $val[$i-$moveleft] = '*'; //comment below line to see which diagonal line is removed unset($val[$i-$moveleft]); $output[$key] = array_values($val); //make keys sequential again $moveleft++; } break; } } echo '<h2>Original Output</h2>'; echo (TestValid($originalOutput, $nullchar)?'valid!!<br />':'INVALID!!<br />'); ShowNice($originalOutput); echo '<h2>Output</h2>'; $valid = TestValid($output, $nullchar); echo ($valid?'valid!!<br />':'INVALID!!<br />'); ShowNice($output); if (!$valid) { $output = $originalOutput; } echo '<h2>Best result</h2>'; ShowNice($output); Result:
Input 0 => ['A', 'B', 'C', 'E', 'G', 'H', 'J', 'K', 'M'] 1 => ['A', 'B', 'C', 'E', 'F', 'G', 'H', 'J'] 2 => ['A', 'B', 'D', 'E', 'G', 'H', 'J', 'K'] 3 => ['A', 'B', 'C', 'D', 'E', 'G', 'I'] 4 => ['A', 'B', 'D', 'E', 'F', 'G'] 5 => ['A', 'B', 'D', 'F', 'G', 'H'] 6 => ['A', 'B', 'C', 'D', 'F', 'G'] 7 => ['A', 'C', 'D', 'F', 'G', 'I'] 8 => ['A', 'C', 'E', 'G', 'H', 'I'] 9 => ['A', 'B', 'C', 'D', 'E', 'F'] Output 0 => ['A', 'B', 'C', 'E', 'G', 'H', 'J', 'K', 'M', '_', '_', '_', '_'] 1 => ['B', 'C', 'E', 'G', 'H', 'J', '_', '_', 'F', '_', '_', '_', 'A'] 2 => ['_', 'E', 'G', 'H', 'J', 'K', '_', '_', 'D', '_', '_', 'A', 'B'] 3 => ['E', 'G', '_', '_', '_', '_', '_', 'D', 'I', '_', 'A', 'B', 'C'] 4 => ['G', '_', '_', '_', '_', 'F', 'D', '_', '_', 'A', 'B', '_', 'E'] 5 => ['H', '_', '_', '_', 'F', 'D', '_', '_', 'A', 'B', '_', '_', 'G'] 6 => ['_', '_', '_', 'F', 'D', '_', '_', 'A', 'B', 'C', '_', 'G', '_'] 7 => ['_', '_', 'F', 'D', 'I', '_', 'A', '_', 'C', '_', 'G', '_', '_'] 8 => ['_', '_', '_', 'I', '_', 'A', '_', 'C', 'E', 'G', 'H', '_', '_'] 9 => ['F', 'D', '_', '_', 'A', 'B', 'C', 'E', '_', '_', '_', '_', '_'] This is the result of the numbers table, as you can see it just moves the entire string one position to the right for each inner array. Then we just exchange the missing values for null chars.
Input 0 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 1 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 2 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 3 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 4 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 5 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 6 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 7 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 8 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 9 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] Output 0 => ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] 1 => ['2', '3', '4', '5', '6', '7', '8', '9', '10', '1'] 2 => ['3', '4', '5', '6', '7', '8', '9', '10', '1', '2'] 3 => ['4', '5', '6', '7', '8', '9', '10', '1', '2', '3'] 4 => ['5', '6', '7', '8', '9', '10', '1', '2', '3', '4'] 5 => ['6', '7', '8', '9', '10', '1', '2', '3', '4', '5'] 6 => ['7', '8', '9', '10', '1', '2', '3', '4', '5', '6'] 7 => ['8', '9', '10', '1', '2', '3', '4', '5', '6', '7'] 8 => ['9', '10', '1', '2', '3', '4', '5', '6', '7', '8'] 9 => ['10', '1', '2', '3', '4', '5', '6', '7', '8', '9'] UPDATE
I updated the code because sometime we had an extra diagonal line of wildcards that's not needed. See the first result. We can unset the diagonal key, unless we need it because we had more rows then distinct values.
Result:
Input 0 => ['A', 'B', 'C', 'E', 'G', 'I', 'J', 'K', 'L'] 1 => ['A', 'B', 'C', 'D', 'F', 'H', 'I', 'J'] 2 => ['A', 'B', 'C', 'E', 'F', 'G', 'H', 'J'] 3 => ['A', 'B', 'C', 'D', 'E', 'F', 'H'] 4 => ['A', 'C', 'D', 'F', 'G', 'I'] 5 => ['A', 'C', 'D', 'E', 'F', 'G'] 6 => ['A', 'B', 'C', 'D', 'E'] 7 => ['A', 'B', 'D', 'E'] 8 => ['A', 'C', 'D'] 9 => ['A', 'B'] Output 0 => ['A', 'B', 'C', 'E', 'G', 'I', 'J', 'K', 'L', '_', '_', '_'] 1 => ['B', 'C', '_', '_', 'I', 'J', '_', '_', 'D', 'F', 'H', 'A'] 2 => ['C', 'E', 'G', '_', 'J', '_', '_', '_', 'F', 'H', 'A', 'B'] 3 => ['E', '_', '_', '_', '_', '_', 'D', 'F', 'H', 'A', 'B', 'C'] 4 => ['G', 'I', '_', '_', '_', 'D', 'F', '_', 'A', '_', 'C', '_'] 5 => ['_', '_', '_', '_', 'D', 'F', '_', 'A', '_', 'C', 'E', 'G'] 6 => ['_', '_', '_', 'D', '_', '_', 'A', 'B', 'C', 'E', '_', '_'] 7 => ['_', '_', 'D', '_', '_', 'A', 'B', '_', 'E', '_', '_', '_'] 8 => ['_', 'D', '_', '_', 'A', '_', 'C', '_', '_', '_', '_', '_'] 9 => ['_', '_', '_', 'A', 'B', '_', '_', '_', '_', '_', '_', '_'] UPDATE with your test:
Best result 0 => ['X', 'Y', 'Z', 'I', 'J'] 1 => ['Y', 'Z', 'I', '_', 'X'] 2 => ['Z', 'I', '_', 'X', 'Y'] 3 => ['I', '_', 'X', 'Y', 'Z'] 4 => ['_', 'X', 'Y', 'Z', '_'] Answers 2
what you should try to use is called a Power set which is:
from wikipedia in mathematics, the power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself, variously denoted as P(S), 𝒫(S), ℘(S) (using the "Weierstrass p"), P(S), ℙ(S), or, identifying the powerset of S with the set of all functions from S to a given set of two elements, 2S.
if have a set of {a,b,c} it would give results of :
{{a,b,c},{a,b},{a,c},{b,c},{a},{b},{c}}
a useful php library from github will give the right results you are looking for in above rules if not all rules applied you can also try to add filters on the results to get them right.
Answers 3
Based off the answer in the previous question you supplied this can be solved ( for that case ) way more elegantly using a few built in functions PHP has for array support. Which is probably the best of any language.
function solve($matrix){ $master = []; $_matrix = []; foreach($matrix as $key => $array){ $_matrix[$key] = array_combine($array,$array); $master += $_matrix[$key]; } $default = array_fill_keys($master, ''); $result = []; foreach($_matrix as $array){ $result[] = array_values(array_merge($default, $array)); } print_r($result); } Using their same tests
$tests = [ [ ['X'], ['X'] ], [ ['X'], ['X'], ['X'] ], [ [ 'X', '' ], [ '', 'X' ] ], [ ['X', 'Y', 'Z'], ['X', 'Y'], ['X']], [ ['X', 'Y'], ['X', 'Y'], ['X', 'Y'] ], [ ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'] ], [ ['X', 'Y', 'Z', 'I', 'J'], ['X', 'Y', 'Z', 'I'], ['X', 'Y', 'Z', 'I'], ['X', 'Y', 'Z', 'I'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'] ], ]; array_map(function ($matrix) { solve($matrix); }, $tests); This is what I get in comparison
[ 0 => ['X', 'Y', 'Z', 'I', 'J'] //<- contains all unique values 1 => ['X', 'Y', 'Z', 'I'] 2 => ['X', 'Y', 'Z', 'I'] 3 => ['X', 'Y', 'Z', 'I'] 4 => ['X', 'Y', 'Z'] 5 => ['X', 'Y', 'Z'] ] Their Result: [ 0 => ['', 'X', 'Y', 'Z', 'I', 'J'] //<- contains an extra '' empty value 1 => ['', '', 'X', 'Y', 'Z', 'I'] 2 => ['I', '', '', 'X', 'Y', 'Z'] 3 => ['Z', 'I', '', '', 'X', 'Y'] 4 => ['Y', 'Z', '', '', '', 'X'] 5 => ['X', 'Y', 'Z', '', '', ''] ] My Result [ 0 => ['X', 'Y', 'Z', 'I', 'J'] 1 => ['X', 'Y', 'Z', 'I', ''] 2 => ['X', 'Y', 'Z', 'I', ''] 3 => ['X', 'Y', 'Z', 'I', ''] 4 => ['X', 'Y', 'Z','',''] 5 => ['X', 'Y', 'Z','',''] ] You can test it here.
http://sandbox.onlinephpfunctions.com/code/86d0b4332963f95449df2e7d4d47fcd8224fe45d
I even timed it using microtime
mine 0.00013017654418945 milliseconds
theirs 0.10895299911499 milliseconds
Which is not really a surprise, as theirs is around 60 lines of code and 7 function calls. Mine is only 1 function 14 lines of code.
That said I don't know if the position of the values are important in the output. Nor exactly what you expect as the output extending that question.
The fact is they also lose the index position, just look at the second array in their result, 2 => ['I', '', '', 'X', 'Y', 'Z'] compared to the input 2 => ['X', 'Y', 'Z', 'I']. And I won't mention the extra '' in the output that probably doesn't belong there.
Maybe I'm missing something, lol, I don't typically do these math-y type things.
UPDATE if you want an explanation of how this works,
array_combine($array,$array);creates an array with matched key => value, we abuse the fact that array keys are unique by nature. Like so['X'=>'X','Y'=>'Y'...]- then we build a "master" array with all the values in it and matched keys, one array to rule them all. The master array is limited in size to the max number or unique values because we are using the keys to eliminate duplicates.
- then we use
array_fill_keys($master, '');to sort of create a template of all the values. The keys of "master" are all the unique values in all of the inner arrays, so we fill it with our "wildcard" placeholder. In this case it looks like this['X'=>'', 'Y'=>'', 'Z'=>'', 'I'=>'', 'J'=>''] - then we merge the "modified" original array, also abusing the array keys for our advantage, by replacing the placeholders in the "templated" master array with the "modified" original array, because the keys match.
- last we strip the keys from the array using
array_values
And we are left with each inner array "templated" by the master array but with the original values filled in and the missing ones empty.
0 comments:
Post a Comment