como encontrar a permutação de multidimensional array em php

Estou tentando consertar este enigma:

Eu tenho uma matriz chamada input :

 $input = [ 'A' => ['X', 'Y', 'Z'], 'B' => ['X', 'Y', 'Z'], 'C' => ['X', 'Y', 'Z'], ]; 

Eu tenho que fazer alguma magia nisso que a matriz de saída tem valor exclusivo na mesma chave em cada matriz, pode parecer fácil, mas não é, essa magia deve adicionar uma string vazia se não houver correspondência para a célula, a única regra é ter um valor exclusivo na mesma chave em cada matriz interna.

 $output = [ 'A' => ['X', 'Y', 'Z'], 'B' => ['Z', 'X', 'Y'], 'C' => ['Y', 'Z', 'X'], ]; 

As regras são:

  1. matriz de saída deve conter matrizes com os mesmos valores da matriz de input,
  2. O curinga só é permitido se não houver correspondência válida para determinado índice
  3. diferentes tamanhos internos são permitidos
  4. Os valores internos da matriz não podem ser duplicados.
  5. matriz de saída deve ter valores exclusivos na mesma chave

exemplo:

 $input = [ 'A' => ['X', 'Y'], 'B' => ['X', 'Y'], 'C' => ['X', 'Y'], ]; 

solução possível:

 $output = [ 'A' => ['X', 'Y', ''], 'B' => ['', 'X', 'Y'], 'C' => ['Y', '', 'X'], ]; 

TL; DR: quadrado a matriz e, em seguida, use força bruta para gerar toda rotação de coluna possível. Quando uma rotação não tem valores de coluna duplicados, pare. Veja-o ao vivo no 3v4l.org.


Minha outra resposta fornece uma solução compacta se e somente se todas as linhas contiverem todos os valores possíveis (em qualquer ordem). Aqui está um exemplo. Minha resposta anterior garante uma solução para a matriz à esquerda, mas não a da direita:

 Satisfies Does not satisfy [ [ [ 'X', 'Y' ], [ 'X', 'Y' ], [ 'Y', 'X' ], [ 'Y' ], ] ] 

Para lidar com o caso geral, onde qualquer linha pode conter qualquer subconjunto arbitrário de todos os valores possíveis, podemos brutar forçar uma solução. Nosso bruto precisa saber como:

  1. Verifique se a matriz está resolvida.
  2. Evoluir sistematicamente a matriz para uma solução.

O primeiro é fácil de escrever. Para cada coluna em uma dada matriz quadrada , verifique se o número de valores exclusivos, não-curinga, difere do número de valores. Se assim for, então, pelo menos, um valor não-curinga é duplicado nessa coluna:

 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; } 

A segunda parte requer um truque. Observe que se pode aplicar um vetor a qualquer matriz quadrada para girar valores na matriz. Vou ignorar a matemática e apenas mostrar alguns exemplos:

 original = [ [ 'X', 'Y' ], [ 'Y', 'X' ], ] vector = [ 0, 0 ] // rotate 1st row 0 places, 2nd row 0 places result = [ [ 'X', 'Y' ], [ 'Y', 'X' ], ] vector = [ 1, 0 ] // rotate 1st row 1 place, 2nd row 0 places result = [ [ 'Y', 'X' ], [ 'Y', 'X' ], ] vector = [ 0, 1 ] // rotate 1st row 0 places, 2nd row 1 place result = [ [ 'X', 'Y' ], [ 'X', 'Y' ], ] vector = [ 1, 1 ] // rotate 1st row 1 place, 2nd row 1 place result = [ [ 'Y', 'X' ], [ 'X', 'Y' ], ] 

Uma vez que existem 2 linhas de 2 colunas cada, existem exatamente 4 combinações de vetores de rotação (todos listados acima). Destes quatro vetores, dois – [ 0, 0 ] e [ 1, 1 ] – produzem uma solução. Uma vez que só precisamos de uma solução, basta parar no primeiro vetor que produz uma matriz resolvida.

Sabendo disso, é aqui como escreveremos o nosso bruto: gerar todos os vetores de rotação possíveis, tentar cada um contra o nosso quebra-cabeça e retornar se a matriz transformada estiver em um estado resolvido:

 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'; } 

Também precisamos de alguns ajudantes, um arnês de teste e alguns testes:

 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'] ], [ ['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) { matrix_display($matrix); echo "solved by:" . PHP_EOL; matrix_brute_solve($matrix); echo PHP_EOL; }, $tests); 

O que produz para esses testes (apenas alguns exemplos):

 [ 0 => ['X', 'Y', 'Z'] 1 => ['X', 'Y', 'Z'] 2 => ['X', 'Y', 'Z'] ] solved by: [ 0 => ['Z', 'X', 'Y'] 1 => ['Y', 'Z', 'X'] 2 => ['X', 'Y', 'Z'] ] [ 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'] ] solved by: [ 0 => ['', 'X', 'Y', 'Z', 'I', 'J'] 1 => ['', '', 'X', 'Y', 'Z', 'I'] 2 => ['I', '', '', 'X', 'Y', 'Z'] 3 => ['Z', 'I', '', '', 'X', 'Y'] 4 => ['Y', 'Z', '', '', '', 'X'] 5 => ['X', 'Y', 'Z', '', '', ''] 

Veja-o ao vivo no 3v4l.org.

O gerador de vetores é O(n n ) tanto no tempo como no espaço. Então, se você tivesse uma matriz quadrada de 3×3, haveria 3 3 = 27 iterações e elementos de matriz armazenados. Para 4×4, você teria 4 4 = 256. Você consegue a ideia. O gerador pode ser melhorado para ser O(1) no espaço , mas sendo que é um algoritmo de profundidade-primeiro, sempre será O(n n ) no tempo.

Além disso, como implementado, o algoritmo pára quando ele encontra a primeira solução. Uma modificação trivial permitirá que você encontre todas as soluções. Uma adição interessante a este quebra-cabeça seria encontrar a solução com o menor número de rotações.

TL; DR: Este código resolve de forma compacta o caso em que todas as linhas contêm todos os valores em qualquer ordem. Para uma solução para o caso geral – cada linha possui um subconjunto de todos os valores possíveis – veja minha outra resposta .


“Se eu tivesse apenas uma hora para resolver um problema, eu gastaria até dois terços dessa hora na tentativa de definir qual é o problema.” – Albert Einstein

Parece que você deseja que uma matriz irregular esteja quadrada sem colunas compartilhando o mesmo pedido. Vamos definir funções para isso:

 function array_make_square(array &$array, $fill = ' ') { $pad = count(array_keys($array)); foreach ($array as &$row) { $row = array_pad($row, $pad, $fill); } } function array_organize(array &$outer) { $offset = 0; foreach ($outer as &$inner) { sort($inner); array_rotate($inner, $offset++); } } function array_rotate(array &$array, $offset) { foreach (array_slice($array, 0, $offset, true) as $key => $val) { unset($array[$key]); $array[$key] = $val; } } 

Agora vamos colocar alguns invólucros em torno desses para testar o comportamento:

 function solve($test) { array_make_square($test); array_organize($test); return $test; } function display($outer) { echo "[\n"; foreach ($outer as $row => $inner) { echo " $row => ['" . implode("', '", $inner) . "']\n"; } echo "]\n"; } $tests = [ [ ['X'], ['X'], ['X'] ], [ ['X', 'Y'], ['X', 'Y'], ['X', 'Y'] ], [ ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'] ], ]; array_map('display', array_map('solve', $tests)); 

O que produz:

 [ 0 => [' ', ' ', 'X'] 1 => [' ', 'X', ' '] 2 => ['X', ' ', ' '] ] [ 0 => [' ', 'X', 'Y'] 1 => ['X', 'Y', ' '] 2 => ['Y', ' ', 'X'] ] [ 0 => ['X', 'Y', 'Z'] 1 => ['Y', 'Z', 'X'] 2 => ['Z', 'X', 'Y'] ] 

Veja-o ao vivo no 3v4l.org.

Estou coletando todas as informações primeiro, ou seja, nomes-chave como ABC, etc., todos os valores como XYZ etc. e número de elementos por cada sub-matriz. Então eu crio novos arrays para cada posição na sub-matriz, ou seja pos0, pos1 e pos2 neste caso. Então, preencho as novas sub-matrizes usando os valores de valArray (escolhendo aleatoriamente), mantendo a restrição de que o valor não deve ser repetido nesta matriz ou em qualquer outra matriz para a mesma posição.

Espero que isto ajude..

   ['X', 'Y', 'Z','P'], 'B' => ['X', 'Y', 'Z','Q'], 'C' => ['X', 'Y', 'Z','R'], 'D' => ['X','Y','K'] ]; // declare two arrays - keyArray will hold all key names like A, B, C // valArray will hold all the distinct values like X, Y, Z // valLength is number of elements in each sub array $keyArray = []; $valArray = []; $valLength =0; // no of elements in sub array echo "
  "; // this loop will gather all the relevenat info for $keyArray, $valAray and $valLength echo "INPUT

"; foreach($input as $key => $val) { if(is_array($val)) { echo "$key
"; $keyArray[] = $key; if(count($val) > $valLength) { $valLength = count($val); } foreach($val as $key1 => $val1) { echo "$key1 => $val1
"; if (! in_array($val1, $valArray)) { //echo "no ..."; $valArray[] = $val1; } } echo "
----
"; } else { // echo "$key => $val
"; } } echo "
"; $output =[]; //create arrays for each position for($i=0; $i<$valLength; $i++) { $posArr = "pos" . $i; $$posArr = []; } foreach($keyArray as $key) { //echo "$key
"; $thisArr = []; for($i=0; $i<$valLength; $i++) { //echo "$i
"; $posArr = "pos" . $i; $whileIterations = 0; // no of random iterations to perform before using wildcard $randomKey=array_rand($valArray); $new = $valArray[$randomKey]; do { $randomKey=array_rand($valArray); $new = $valArray[$randomKey]; $whileIterations++; if($whileIterations > 10) { // no of iterations ls limited to 10 $new = ''; break; } }while(in_array($new,$thisArr) || in_array($new, $$posArr)); $thisArr[] = $new; //$$posArr[] = $new; if($new != '') { array_push($$posArr,$new); // keep this in position array so that same value is not repeated in the same position } } // now one subarray is ready to be assigned $keyName = $key; $$keyName = []; $$keyName = $thisArr; } // push sub arrays into output array foreach($keyArray as $key) { $keyName = $key; //echo "$keyName
"; foreach ($$keyName as $key2) { // echo "$key2
"; } //echo "
----
"; //array_push($output, $$keyName); $output[$keyName] = $$keyName; } echo "OUTPUT

"; foreach($output as $key => $val) { if(is_array($val)) { echo "$key
"; $keyArray[] = $key; foreach($val as $key1 => $val1) { echo "$key1 => $val1
"; } } echo "
----
"; } echo "
 
"; ?>

Você pode usar array_shift para criar uma matriz com todos os elementos. Em seguida, configure o elemento perdido para '' . O código abaixo é bem comentado. https://eval.in/895863

  ['X', 'Z'], 'B' => ['X', 'Z'], 'C' => ['X', 'Z'], ]; // element not in $inpupt $diff = array_diff($vs, $input[$ks[0]]); // array with all the values $arr = []; foreach($ks as $k) { $arr[$k] = $vs; array_push($vs, array_shift($vs)); } // set value in the $diff array to '' $result = array_map(function($value) use ($diff) { return array_map( function($v) use ($diff) { return in_array($v, $diff) ? '' : $v; }, $value); }, $arr); print_r($result); 

Edite para o comentário do OP

Para a $input com elemento diferente, a matriz $diff deve ser calculada separadamente. https://eval.in/896322

  ['X', 'Z'], 'B' => ['X', 'Z'], 'C' => ['X', 'A'], ]; // array with all the values $arr = []; foreach($ks as $k) { $arr[$k] = $vs; array_push($vs, array_shift($vs)); } // set value in the $diff array to '' $result = array_map(function($value, $k) use ($input, $vs) { // element not in $inpupt[$k] $diff = array_diff($vs, isset($input[$k]) ? $input[$k] : []); return array_map( function($v) use ($diff) { return in_array($v, $diff) ? '' : $v; }, $value); }, $arr, $ks); // when use multi array for `array_map` the index lost, so combine index with the result here. $result = array_combine($ks, $result); print_r($result); 

ok, eu acho que estamos perto agora, eu tenho essa idéia, há uma coisa a fazer, descreveu-a no final

  1. aumentar o tamanho da matriz de input para o número de elementos das ocorrências mais altas ou o comprimento mais alto da criança depende do que é bugger
  2. tente encontrar todas as placas para X , depois tentando todos os lugares para Y e assim por diante.
  3. Toda vez que a encontrar, adicione-a à matriz que mantém elementos usados ​​para evitar duplicatas.

ajudantes:

 function getHeight($array) { $max2 = $max1 = 0; $max = []; foreach ($array as $k => $v) { if ($max2 < count($v)) { $max2 = count($v); } foreach($v as $elem) { if(isset($max[$elem])) { $max[$elem]++; } else { $max[$elem] = 1; } } } foreach($max as $m) { if ($max1 < $m) { $max1 = $m; } } return max($max2, $max1); } function getRow($array, $j) { $res = []; foreach ($array as $k => $v) { $res[] = $v[$j] ?? ''; } return $res; } 

código

 function solve_this_array_please() { $input = [ 'A' => ['X', 'Y', 'Z', 'I'], 'B' => ['X', 'Y', 'Z', 'I'], 'C' => ['X', 'Y', 'Z', 'I'], 'D' => ['X', 'Y', 'Z', 'I'], ]; usort($input, function($i, $j) { return count($i) <=> count($j); }); $output = []; $h = getHeight($input); // filling te missing wildcards; foreach($input as $k => $v) { for($i=0;$i<$h;$i++) { if (!isset($input[$k][$i])) $input[$k][$i] = ''; } $output[$k] = []; $used[$k] = []; } $j = 0; foreach($input as $key2 => $col2) { foreach($col2 as $k => $elem) { foreach($input as $key => $col) { for($i=0;$i<$h;$i++) { dump("TRYING: $key $i = $elem"); if (!in_array($elem, getRow($output, $i)) && !in_array($elem, $used[$key]) && (!isset($output[$key][$i]) || $output[$key][$i] == '')) { if (in_array($elem, $col)) { dump("ok"); $output[$key][$i] = $elem; $used[$key][] = $elem; $i = 0; break; } } } } } } foreach($output as $k => $o) { ksort($output[$k]); } dump($output); } 

uma coisa com a qual ainda preciso de ajuda é fazer esse script para começar a procurar próxima matriz na chave quando ele encontrar a última em vez de 0