php - attribute - Consejos de rendimiento para encontrar permutación única

title html css

Question

TLDR: ¿cómo encontrar la permutación de matrices multidimensionales en php y cómo optimizar para matrices más grandes?

Esta es la continuación de esta pregunta: cómo encontrar la permutación de matriz multidimensional en php

tenemos un script para ordenar la matriz, la idea es encontrar una permutación única de la matriz, las reglas para encontrar esta permutación son

1. La matriz de entrada contiene un conjunto de matrices.
2. Cada matriz interna contiene elementos únicos.
3. Cada matriz interna puede tener diferente longitud y diferentes valores.
4. La matriz de salida debe contener exactamente los mismos valores.
5. La matriz interna de salida debe tener valores únicos en la misma clave.
6. Si no hay solución, comodín ie.: null están permitidos.
7. Los comodines se pueden duplicar en la misma clave.
8. La solución debe tener la menor cantidad de comodines posibles.
9. El algoritmo debe poder manejar un arreglo de hasta 30x30 en menos de 180 s.

Tengo esta solución hasta ahora:

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

Y esto funciona perfectamente en una pequeña matriz, pero el problema es esta iteración sobre todas las posibilidades de movimientos de una matriz, y para una matriz como 6x6, esto es demasiado para calcular: ¡ O(n n ) tanto en tiempo como en espacio!

Answer 1

Basándose en la respuesta a la pregunta anterior que proporcionó, esto se puede resolver (en ese caso) de manera más elegante utilizando algunas funciones incorporadas que PHP tiene para el soporte de matriz. Cuál es probablemente el mejor de cualquier idioma.

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

Usando sus mismas pruebas.

$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);

Esto es lo que obtengo en comparación

[
  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'','''','''']
]

Puedes probarlo aquí.

http://sandbox.onlinephpfunctions.com/code/86d0b4332963f95449df2e7d4d47fcd8224fe45d

Incluso lo cronometré usando microtime

mina 0.00013017654418945 milisegundos

suyos 0.10895299911499 milisegundos

Lo que no es realmente una sorpresa, ya que tienen alrededor de 60 líneas de código y 7 llamadas de función. El mío es solo 1 función 14 líneas de código

Dicho esto, no sé si la posición de los valores es importante en la salida. Tampoco es exactamente lo que esperas como la salida que extiende esa pregunta

El hecho es que también pierden la posición del índice, solo mire la segunda matriz en su resultado, 2 => [''I'', '''', '''', ''X'', ''Y'', ''Z''] comparación con la entrada 2 => [''X'', ''Y'', ''Z'', ''I''] . Y no mencionaré el '''' extra '''' en la salida que probablemente no pertenezca allí.

Tal vez me esté perdiendo algo, jajaja, normalmente no hago estas cosas de tipo matemático.

ACTUALIZAR si desea una explicación de cómo funciona esto,

• array_combine($array,$array); crea una matriz con clave = = valor coincidente, abusamos del hecho de que las claves de matriz son únicas por naturaleza Al igual que [''X''=>''X'',''Y''=>''Y''...]
• luego construimos una matriz "maestra" con todos los valores y claves combinadas, una matriz para gobernarlos a todos. La matriz maestra está limitada en tamaño al número máximo o valores únicos porque estamos usando las claves para eliminar duplicados.
• luego usamos array_fill_keys($master, ''''); Para ordenar de crear una plantilla de todos los valores. Las claves de "maestro" son todos los valores únicos en todos los arreglos internos, por lo que lo llenamos con nuestro marcador de posición "comodín". En este caso, se ve así: [''X''=>'''', ''Y''=>'''', ''Z''=>'''', ''I''=>'''', ''J''=>'''']
• luego fusionamos la matriz original "modificada", y también abusamos de las claves de la matriz para nuestra ventaja, reemplazando los marcadores de posición en la matriz maestra "con plantilla" por la matriz original "modificada", porque las claves coinciden.
• Por último, eliminamos las claves de la matriz utilizando array_values

Y quedamos con cada matriz interna "templada" por la matriz maestra pero con los valores originales rellenados y los que faltan están vacíos.

Answer 2

Después de un poco de violín, se me ocurrió el siguiente código.

La idea es identificar elementos en conflicto y cambiarlos a una columna donde ya no sean un problema. Para los casos en que esto no es aplicable, se realiza una selección aleatoria. El código funciona de forma recursiva y, por lo tanto, hay casos extremos en los que se tarda mucho en completarse.

Un caso extremo extremo es una entrada donde todas las filas consisten exactamente en los mismos valores.

<?php
declare(strict_types=1);

final class SwapSolver
{
    /**
     * @param array $input
     *
     * @return array
     */
    public function solve(array $input): array
    {
        $input = array_values($input);

        return $this->swapDuplicates($this->prepare($input, $this->getMinRowLength($input)));
    }

    /**
     * @param array $input
     *
     * @return array
     */
    private function swapDuplicates(array $input): array
    {
        $unswappable = [];

        foreach ($this->duplicates($input) as $position) {
            list($r, $a) = $position;

            $swapped = false;
            foreach ($this->swapCandidates($input, $r, $a, true) as $b) {
                $input[$r] = $this->swap($input[$r], $a, $b);
                $swapped = true;
                break;
            }

            if (!$swapped) {
                $unswappable[] = $position;
            }
        }

        // still unswappable
        $unswappable = array_values(array_filter($unswappable, function (array $position) use ($input): bool {
            return $this->isDuplicate($input, ...$position);
        }));

        // tie breaker
        if (count($unswappable) > 0) {
            list($r, $a) = $unswappable[mt_rand(0, count($unswappable) - 1)];

            $candidates = [];
            foreach ($this->swapCandidates($input, $r, $a, false) as $b) {
                $candidates[] = $b;
            }

            $input[$r] = $this->swap($input[$r], $a, $candidates[mt_rand(0, count($candidates) - 1)]);

            return $this->swapDuplicates($input);
        }

        return $input;
    }

    /**
     * @param array $input
     *
     * @return /Generator
     */
    private function duplicates(array &$input): /Generator
    {
        foreach ($input as $r => $row) {
            foreach ($row as $c => $value) {
                if ($this->isDuplicate($input, $r, $c)) {
                    yield [$r, $c];
                }
            }
        }
    }

    /**
     * @param array $input
     * @param int   $row
     * @param int   $column
     *
     * @return bool
     */
    private function isDuplicate(array $input, int $row, int $column): bool
    {
        $candidate = $input[$row][$column];

        if (is_null($candidate)) {
            return false;
        }

        foreach (array_column($input, $column) as $r => $value) {
            if ($r !== $row && $value === $candidate) {
                return true;
            }
        }

        return false;
    }

    /**
     * @param array $input
     * @param int   $row
     * @param int   $column
     * @param bool  $strict
     *
     * @return /Generator
     */
    private function swapCandidates(array &$input, int $row, int $column, bool $strict): /Generator
    {
        foreach ($input[$row] as $c => $dst) {
            if ((!$strict || !in_array($input[$row][$column], array_column($input, $c), true))
                && (is_null($dst) || !in_array($dst, array_column($input, $column), true))
            ) {
                yield $c;
            }
        }
    }

    /**
     * @param array $row
     * @param int   $from
     * @param int   $to
     *
     * @return array
     */
    private function swap(array $row, int $from, int $to): array
    {
        $tmp = $row[$to];
        $row[$to] = $row[$from];
        $row[$from] = $tmp;

        return $row;
    }

    /**
     * @param array $input
     * @param int   $padSize
     *
     * @return array
     */
    private function prepare(array $input, int $padSize): array
    {
        return array_map(function (array $row) use ($padSize): array {
            $row = array_pad($row, $padSize, null);
            shuffle($row);

            return $row;
        }, $input);
    }

    /**
     * @param array $input
     *
     * @return int
     */
    private function getMinRowLength(array $input): int
    {
        return max(
            ...array_values(array_count_values(array_merge(...$input))),
            ...array_map(''count'', $input)
        );
    }
}

Uso:

<?php
$solver = new SwapSolver();
$solution = $solver->solve($input);

Más código en: https://github.com/Yoshix/so-47261385

Answer 3

Espero que esta sea la solución que estamos buscando. Solicito a todos que revisen mi solución.

el código:

<?php
$input = [
    [ ''F'', ''I'', ''J'', ''Z'' ],
    [ ''F'', ''R'', ''U'', ''V'' ],
    [ ''I'', ''R'', ''U'', ''V'' ],
    [ ''M'', ''P'', ''U'', ''V'' ],
];
do {
    $result = calculate($input);
} while(!TestValid($input, $result, ''_''));


echo (TestValid($input, $result, ''_'')) ? ''VALID'' : ''INVALID'';

ShowNice($result);

function TestValid($input, $output, $nullchar) {

    foreach($output as $k => $o) {
        $test = array_filter($o, function($v) use ($nullchar) {
            return $v != $nullchar;
        });

        if (count($test) != count($input[$k])) {
            return false;
        }
    }
    return true;
}

function ShowNice($output) {
    $height = getHeight($output);

  foreach($output as $k => $v ) {
        for($i = 0;$i < $height;$i ++) {

            if (!isset($output[$k][$i])) {
                $output[$k][$i] = ''_'';
            }
        }
    }

  echo ''<pre>'';
  foreach($output as $key=>$val) {
    echo ''<br />'' . str_pad($key,2," ",STR_PAD_LEFT) . '' => ['';
    ksort($val);
    echo join('', '', $val);
    echo '']'';
  }
  echo ''</pre>'';
}

function calculate($array) {

    echo "<pre>";
    $full = getFullList($array);

    foreach($full as $f) {
        $frequency[$f] = getFrequency($array, $f);
    }

    // uksort($frequency, function($i, $j) use ($frequency) { 
    //     return $frequency[$j] <=> $frequency[$i];
    // });

    $frequency = array_keys($frequency);

    shuffle($frequency);


    $height = getHeight($array);

    foreach($array as $k => $v ) {
        for($i = 0;$i < $height;$i ++) {
            if (!isset($array[$k][$i]))
                $array[$k][$i] = ''_'';
        }
    }

    foreach($array as $key => $value ) {
        $output[$key] = [];
        $used[$key] = [];
    }

    foreach($array as $key => $value ) {
        foreach($frequency as $k => $v) {

            $j = 0;

            foreach($array as $kk => $col) {
                if (in_array($v, $col)) {
                    for ($h = 0; $h <= $height; $h++) {

                        if (!isset($_h[$v][$kk])) {
                            $_h[$v][$kk] = 0;
                        }

                        if ($h + $_h[$v][$kk] >= $height) {
                            $hh = ($h + $_h[$v][$kk]) - $height;
                        } else {
                            $hh = $h + $_h[$v][$kk];
                        }
                        $row = getRow($output, $hh);
                        if (!in_array($v, $row) && !in_array($v, $used[$kk])) {
                            if (!isset($output[$kk][$hh]) || $output[$kk][$hh] == ''_'') {
                                $output[$kk][$hh] = $v;
                                $used[$kk][] = $v;

                                $keys = array_keys($array);
                                foreach($keys as $i => $ke) {
                                    if ($ke == $kk) {
                                        if(isset($keys[$i+1])) {
                                            $_h[$v][$keys[$i + 1]] = $hh;
                                        } else {
                                            $_h[$v][$keys[0]] = $hh;
                                        }
                                    }
                                }
                               $unused[$kk] = array_diff($col, $used[$kk]);
                                $j++;
                                break;
                            }
                        }
                    }
                }
            }

            // ShowNice($output);
        }

    }
    foreach($output as $k => $v ) {
        for($i = 0;$i < $height;$i ++) {
            if (!isset($output[$k][$i]))
                $output[$k][$i] = ''_'';
        }
    }

    foreach($output as $k => $o) {
        ksort($output[$k]);
    }

    return $output;
}

function getHeight($array) {
    $heights = [];
    $max3 = count($array);
    $max2 = 0;
    foreach($array as $v) {
        if ($max2 < count($v)) {
            $max2 = count($v);
        }

        foreach ($v as $e) {
            $heights[$e] = (isset($heights[$e])) ? $heights[$e] + 1 : 1;
        }

    }
    $max = 0;
    foreach ($heights as $h ) {
        if ($h > $max) {
            $max = $h;
        }
    }

    return max($max, $max2, $max3);
}

function getRow($array, $row) {
    $res = [];
    foreach ($array as $a) {
        if (is_array($a)) {
            foreach($a as $k =>$b) {
                if ($row == $k) {
                    $res[] = $b;
                }
            }
        }
    }

    return $res;
}

function getFrequency($array, $value) {
    $c=0;
    foreach ($array as $key => $v) {
        foreach ($v as $e) {
            if ($e == $value) 
                $c++;
        }
    }
    return $c;
}

function getFullList($array) {

    $m = [];
    foreach($array as $a) {
        $m = array_merge($m, $a);
    }

    return array_unique($m);
}

ACTUALIZADO

Este puede ser el final, verifique por favor: playground : https://eval.in/906355

Answer 4

La solución es bastante simple en realidad. Verifica el número de caracteres únicos y ese es el número de valores en la matriz de salida. A continuación el código hará lo que quieras casi al instante.

La parte difícil es eliminar los comodines. Esto es algo que solo puede hacer con la fuerza bruta si quiere un 100% de certeza. La solución a continuación intentará eliminar todos los comodines cambiando de posición varias veces en orden.

Esto es similar a la manera en que Google maneja el problema del vendedor ambulante en sus herramientas OR. Necesitas encontrar la mejor combinación entre precisión y velocidad. Al establecer el número de bucles más alto en la siguiente función, aumentan las posibilidades de éxito. Pero será más lento.

/* 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'']
];

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

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

$input9 = [
  [''X'', ''Z'', ''Y'', ''A'', ''E'', ''D''],
  [''X'', ''Z'', ''Y'', ''A'', ''B''],
  [''X'', ''Z'', ''Y'', ''A'', ''C''],
  [''X'', ''Z'', ''Y'', ''A'', ''D''],
  [''X'', ''Z'', ''Y'', ''A'', ''D''],
  [''X'', ''Z'', ''Y'', ''A'', ''D'']
];

/* ACTUAL CODE */

CreateOutput($input, 1);

function CreateOutput($input, $loops=0) {


  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 && count($distinct)>$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++;
  }

  echo ''<h2>First output, unchecked</h2>'';
  ShowNice($output);

  $newOutput = $output;
  for ($x=0;$x<=$loops;$x++) {
    $newOutput = MoveLeft($newOutput, $nullchar);
    $newOutput = MoveLeft($newOutput, $nullchar, true);
    $newOutput = SwitchChar($newOutput, $nullchar);
  }

  echo ''<h2>New output</h2>'';
  ShowNice($newOutput);
  //in $newoutput we moved all the invalid wildcards to the end
  //now we need to test if the last row has wildcards

  if (count($newOutput[0])<count($output[0])) {
    $output = $newOutput;
  }


  echo ''<h2>Best result (''.(TestValid($output, $nullchar)?''VALID'':''INVALID'').'')</h2>'';
  ShowNice($output);

  return $output;
}

function MoveLeft($newOutput, $nullchar, $reverse=false) {
  //see if we can remove more wildcards
  $lastkey = count($newOutput[0])-1;
  $testing = true;
  while ($testing) {
    $testing = false; //we decide if we go another round ob_deflatehandler
    $test = $newOutput;

    $lastkey = count($newOutput[0])-1;

    $start = 0;
    $end = count($test);
    if ($reverse) {
      $start = count($test)-1;
      $end = -1;
    }

    for($key = $start;$key!=$end;$key += ($reverse?-1:1) ) {
      $val = $test[$key];
      $org = array_values($val);
      foreach($val as $i=>$char) {
        if ($char!=$nullchar) {
          continue; //we only test wildcards
        }


        $wildcardAtEnd=true;
        for($x=$i+1;$x<=$lastkey;$x++) {
          $nextChar = $val[$x];
          if ($nextChar!=$nullchar) {
            $wildcardAtEnd = false;
            break;
          }
        }


        if ($wildcardAtEnd===true) {
          continue; //the char next to it must not be wildcard
        }

        //remove the wildcard and add it to the base64_encode
        unset($val[$i]);
        $val[] = $nullchar;
        $test[$key] = array_values($val); //correct order

        if (TestValid($test, $nullchar)) {
          //we can keep the new one
          $newOutput = $test;
          $testing = true; //keep testing, but start over to make sure we dont miss anything
          break 2; //break both foreach, not while
        }

        $test[$key] = $org; //reset original values before remove for next test
      }
    }
  }

  $allWildCards = true;
  while ($allWildCards) {
    $lastkey = count($newOutput[0])-1;
    foreach($newOutput as $key=>$val) {
      if ($val[$lastkey]!=$nullchar)  {
        $allWildCards = false;
        break;
      }
    }
    if ($allWildCards) {
      foreach($newOutput as $key=>$val) {
        unset($val[$lastkey]);
        $newOutput[$key] = array_values($val);
      }
      $output = $newOutput;
    }
  }

  return $newOutput;
}

function SwitchChar($newOutput, $nullchar) {
  $switching = true;
  $switched = [];
  while($switching) {
    $switching = false;

    $test = $newOutput;
    $lastkey = count($newOutput[0])-1;

    foreach($test as $key=> $val) {
      foreach($val as $index=>$char) {
        $switched[$key][$index][$char] = true;//store the switches we make

        //see if can move the char somewhere else
        for($i=0;$i<=$lastkey;$i++)
        {
          if ($i==$index) {
            continue;//current pos
          }
          if (isset($switched[$key][$i][$char])) {
            continue; //been here before
          }

          $org = array_values($val);
          $switched[$key][$i][$char] = true;
          $t = $val[$i];
          $val[$index] = $t;
          $val[$i] = $char;
          $test[$key] = array_values($val);

          if (TestValid($test, $nullchar)) {
            //echo ''<br />VALID: '' . $key . '' - '' . $index . '' - '' . $i . '' - '' . $t . '' - '' . $char;
            $newOutput = MoveLeft($test, $nullchar);
            $switching = true;
            break 3;//for and two foreach
          }

          //echo ''<br />INVALID: '' . $key . '' - '' . $index . '' - '' . $i . '' - '' . $t . '' - '' . $char;
          $val = $org;
          $test[$key] = $org;
        }
      }
    }
  }

  return $newOutput;
}

Resultado:

Input

   0 => [''X'', ''Y'', ''A'']
   1 => [''X'', ''Y'', ''B'']
   2 => [''X'', ''Y'', ''C'']

   First output, unchecked

   0 => [''X'', ''Y'', ''A'', ''_'', ''_'']
   1 => [''Y'', ''_'', ''B'', ''_'', ''X'']
   2 => [''_'', ''_'', ''C'', ''X'', ''Y'']

   New output

   0 => [''X'', ''Y'', ''A'', ''_'', ''_'']
   1 => [''Y'', ''B'', ''X'', ''_'', ''_'']
   2 => [''C'', ''X'', ''Y'', ''_'', ''_'']

   Best result (VALID)

   0 => [''X'', ''Y'', ''A'']
   1 => [''Y'', ''B'', ''X'']
   2 => [''C'', ''X'', ''Y'']

Answer 5

lo que deberías intentar usar se llama un conjunto de potencia que es:

de wikipedia en matemáticas, el conjunto de potencias (o el conjunto de potencias) de cualquier conjunto S es el conjunto de todos los subconjuntos de S, incluidos el conjunto vacío y la propia S, designados de forma diversa como P (S), 𝒫 (S), ℘ (S) (usando el "Weierstrass p"), ​​P (S), ℙ (S), o identificando el conjunto de potencias de S con el conjunto de todas las funciones de S a un conjunto dado de dos elementos, 2S.

si tiene un conjunto de {a,b,c} daría resultados de:

{{a,b,c},{a,b},{a,c},{b,c},{a},{b},{c}}

una biblioteca php útil de github le dará los resultados correctos que está buscando en las reglas anteriores. Si no se aplican todas las reglas, también puede intentar agregar filtros a los resultados para obtener los resultados correctos.