как найти перестановку многомерного массива в переполнении стека

Я пытаюсь исправить эту загадку:

У меня есть массив под названием input:

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

Я должен сделать некоторую магию, чтобы выходной массив имел уникальное значение для одного и того же ключа в каждом массиве, может выглядеть легко, но это не так, эта магия должна добавить пустую строку, если нет совпадения для ячейки, единственное правило — иметь уникальное значение на тот же ключ на каждом внутреннем массиве.

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

Правила таковы:

  1. выходной массив должен содержать массивы с такими же значениями из входного массива,
  2. Подстановочные знаки допускаются только в том случае, если для данного индекса нет действительного соответствия
  3. допускаются разные размеры внутреннего массива
  4. значения внутреннего массива не могут дублироваться.
  5. выходной массив должен иметь уникальные значения на одном и том же ключе

пример:

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

возможное решение:

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

1

Решение

TL; DR: Выровняйте матрицу по квадрату, затем используйте грубую силу для генерации каждого возможного вращения столбца. Если один поворот не имеет повторяющихся значений столбцов, остановитесь. Смотрите это в прямом эфире на 3v4l.org.


Мой другой ответ обеспечивает компактное решение если и только если все строки содержат все возможные значения (в любом порядке). Вот пример. Мой предыдущий ответ гарантирует решение для матрицы слева, а не справа:

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

Чтобы справиться с общим случаем, когда любая строка может содержать любое произвольное подмножество всех возможных значений, мы можем грубо форсировать решение. Наш скот должен знать, как:

  1. Проверьте, решена ли матрица.
  2. Систематически развивать матрицу к решению.

Первый легко написать. Для каждого столбца в данном квадратная матрица, проверьте, отличается ли количество уникальных, не подстановочных значений от количества значений. Если это так, то в этом столбце дублируется хотя бы одно не подстановочное значение:

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

Вторая часть требует хитрости. Заметьте, что можно применять вектор к любой квадратной матрице, чтобы вращать значения в матрице. Я пропущу математику и просто покажу несколько примеров:

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

Поскольку имеется 2 строки по 2 столбца в каждой, существует ровно 4 комбинации векторов вращения (все они перечислены выше). Из этих четырех векторов два — [ 0, 0 ] а также [ 1, 1 ] — найти решение. Поскольку нам нужно только одно решение, достаточно остановиться на первом векторе, который дает решенную матрицу.

Зная это, вот как мы напишем наш грубый метод: сгенерируем все возможные векторы вращения, попробуем каждый из них против нашей головоломки и вернемся, если преобразованная матрица находится в решенном состоянии:

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

Который производит для тех тестов (только несколько примеров):

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

Смотрите это в прямом эфире на 3v4l.org.

Генератор вектора O(nn) в и то и другое время а также пространство. Итак, если бы у вас была квадратная матрица 3х3, было бы 33 = 27 итераций и хранимых элементов массива. Для 4х4 у вас будет 44 = 256 Вы поняли идею. Генератор может быть улучшен, чтобы быть O(1) в пространство, но, поскольку это алгоритм глубины, он всегда будет O(nn) во время.

Кроме того, как реализовано, алгоритм останавливается, когда находит первый решение. Тривиальная модификация позволит вам найти все решения. Интересным дополнением к этой головоломке было бы найти решение с малочисленнее севообороты.

3

Другие решения

TL; DR: Этот код компактно решает случай, когда все строки содержат все значения в любой порядок. Для решения общего случая — каждый строка имеет подмножество всех возможные значения — см. мой другой ответ.


«Если бы у меня был только один час для решения проблемы, я бы потратил до двух третей этого часа, пытаясь определить, в чем заключается проблема». — Альберт Эйнштейн

Похоже, вы хотите, чтобы рваный массив был в квадрате без столбцов с одинаковым порядком. Давайте определим функции для этого:

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

Теперь давайте поместим несколько оберток вокруг них, чтобы проверить поведение:

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

Который производит:

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

Смотрите это в прямом эфире на 3v4l.org.

3

Сначала я собираю всю информацию, т. Е. Имена ключей, такие как A B C и т. Д., Все значения, такие как X Y Z и т. Д., И количество элементов в каждом подмассиве. Затем я создаю новые массивы для каждой позиции в подмассиве, а именно в этом случае pos0, pos1 и pos2. Затем я заполняю новые вложенные массивы, используя значения из valArray (случайный выбор), сохраняя ограничение на то, что значение не должно повторяться в этом или любом другом массиве для той же позиции.

Надеюсь это поможет..

    <?php

$input = [
'A' => ['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 "<table width='100%'> <tr> <td width='20%'>&nbsp; </td> <td width='30%'>";
// this loop will gather all the relevenat info for $keyArray, $valAray and $valLength
echo "INPUT <br><br>";
foreach($input as $key => $val) {
if(is_array($val)) {
echo "$key <br/>";
$keyArray[] = $key;
if(count($val) > $valLength) {
$valLength = count($val);
}

foreach($val as $key1 => $val1) {
echo "$key1 => $val1<br>";
if (! in_array($val1, $valArray)) {
//echo "no ...";
$valArray[] = $val1;
}
}
echo "<br>----<br>";
}
else {
// echo "$key => $val<br>";
}
}
echo "</td><td width='30%'>";

$output =[];

//create arrays for each position

for($i=0; $i<$valLength; $i++) {
$posArr = "pos" . $i;
$$posArr = [];
}

foreach($keyArray as $key) {
//echo "$key <br/>";
$thisArr = [];
for($i=0; $i<$valLength; $i++) {
//echo "$i <br>";
$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 <br>";
foreach ($$keyName as $key2) {
// echo "$key2 <br/>";
}
//echo "<br>----<br>";
//array_push($output, $$keyName);
$output[$keyName] = $$keyName;
}

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

}

echo "</td><td width='20%'>&nbsp; </td></tr></table>";

?>
1

Ты можешь использовать array_shift сделать массив со всеми элементами. Затем установите потерянный элемент в '', Ниже код хорошо прокомментирован. https://eval.in/895863

<?php
$ks = ['A', 'B', 'C', 'D'];
$vs = ['X', 'Y', 'Z', 'A'];

$input = [
'A' => ['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);

Изменить для комментария ОП

Для $input с другим элементом, то $diff массив должен рассчитываться отдельно. https://eval.in/896322

<?php
$ks = ['A', 'B', 'C', 'D', 'E'];
$vs = ['X', 'Y', 'Z', 'A'];

$input = [
'A' => ['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);
0

хорошо, я думаю, что мы близки, теперь у меня есть эта идея, есть одна вещь, которую нужно сделать, описал ее в конце

  1. увеличение размера входного массива до числа элементов с наивысшими значениями или наивысшей длиной дочернего элемента зависит от того, что является ошибкой
  2. попытаться найти все места для X, а затем пытается все места для Y и так далее.
  3. каждый раз, когда его находят, добавляют его в массив, который хранит используемые элементы, чтобы избежать дублирования.

помощники:

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

код

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

одна вещь, в которой мне все еще нужна помощь, — заставить этот скрипт начать поиск следующего массива по ключу, когда он найдет последний вместо 0

-1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector