如何在php中找到多维数组排列 [英] how to find multidimensional array permutation in php
问题描述
我正在解决这个谜题:
我有一个名为input的数组:
$input = [
'A' => ['X', 'Y', 'Z'],
'B' => ['X', 'Y', 'Z'],
'C' => ['X', 'Y', 'Z'],
];
我必须做一些魔术，输出数组在每个数组的相同键上具有唯一值，看起来很简单，但并非如此，如果没有匹配的单元格，则该魔术应该添加空字符串，唯一的规则是每个内部数组的相同键上都有唯一的值.
I have to do some magic on it that the output array have unique value on same key on each array, may looks easy but is not, this magic should add empty string if there is no match for cell, only rule is to have unique value on same key on each inner array.
$output = [
'A' => ['X', 'Y', 'Z'],
'B' => ['Z', 'X', 'Y'],
'C' => ['Y', 'Z', 'X'],
];
规则是:
- 输出数组必须包含与输入数组具有相同值的数组，
- 仅在给定索引没有有效匹配的情况下才允许使用通配符
- 允许使用不同的内部数组大小
- 内部数组值不能重复.
- 输出数组在同一键上必须具有唯一值
- output array must contain arrays with same values from input array,
- wildcard are only allowed if there is no valid match for given index
- different inner array sizes are allowed
- inner array values can't duplicate.
- output array must have unique values on the same key
示例:
$input = [
'A' => ['X', 'Y'],
'B' => ['X', 'Y'],
'C' => ['X', 'Y'],
];
可能的解决方案:
$output = [
'A' => ['X', 'Y', ''],
'B' => ['', 'X', 'Y'],
'C' => ['Y', '', 'X'],
];
推荐答案
TL; DR:对矩阵求平方，然后使用蛮力生成所有可能的列旋转.如果一转没有重复的列值，请停止. 在3v4l.org上直播.
TL;DR: Square the matrix, then use brute force to generate every possible column rotation. When one rotation has no duplicate column values, stop. See it live on 3v4l.org.
我的其他答案提供了一个紧凑的解决方案当且仅当所有行都包含所有可能值(以任何顺序).这是一个例子.我先前的答案保证可以解决左侧矩阵的问题，但不能解决右侧矩阵的问题:
My other answer provides a compact solution if and only if all rows contain all possible values (in any order). Here's an example. My previous answer guarantees a solution to the matrix on the left, but not the one on the right:
Satisfies Does not satisfy
[ [
[ 'X', 'Y' ], [ 'X', 'Y' ],
[ 'Y', 'X' ], [ 'Y' ],
] ]
要处理一般情况，即任何行可能包含所有可能值的任意子集，我们可以蛮力解决.我们的蛮横人士需要知道如何:
To handle the general case where any row may contain any arbitrary sub-set of all possible values, we can brute force a solution. Our brute needs to know how to:
- 检查矩阵是否求解.
- 系统地将矩阵演化为解.
第一个很容易编写.对于给定的方阵中的每一列，请检查唯一，非通配符的数量值与值的数量不同.如果是这样，则在该列中至少复制一个非通配符值:
The first one is easy to write. For every column in a given a square matrix, check if the number of unique, non-wildcard values differs from the number of values. If so, then at least one non-wildcard value is duplicated in that column:
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;
}
第二部分需要技巧.观察到可以将向量应用于任何方阵以旋转矩阵中的值.我将跳过数学，仅显示一些示例:
The second part requires a trick. Observe that one can apply a vector to any square matrix to rotate values in the matrix. I'll skip the math and just show some examples:
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 ]-产生一个解.由于我们只需要一个解决方案，因此只要停在产生已解决矩阵的第一个向量上就足够了.
Since there are 2 rows of 2 columns each, there are exactly 4 combinations of rotation vectors (all listed above). Of these four vectors, two - [ 0, 0 ] and [ 1, 1 ] - produce a solution. Since we only need one solution, it's sufficient to stop on the first vector that produces a solved matrix.
知道了这一点，这就是我们编写粗俗的方法:生成所有可能的旋转向量，对每个难题进行尝试，然后返回转换后的矩阵是否处于已求解状态:
Knowing this, here's how we'll write our brute: generate all possible rotation vectors, try each one against our puzzle, and return if the transformed matrix is in a solved state:
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';
}
我们还需要一些帮助程序，测试工具和一些测试:
We'll also need some helpers, a test harness, and some tests:
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);
这些测试产生的内容(仅举几个例子):
Which produces for those tests (just a few examples):
[
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', '', '', '']
向量生成器在时间和空间中都是O(nn).因此，如果您有一个3x3的正方形矩阵，那么将有3 3 = 27次迭代并存储了数组元素.对于4x4，您将有4 4 =256.您会明白的.可以将生成器改进为 space 中的O(1)，但是由于它是深度优先算法，因此在时间上始终为O(nn).
The vector generator is O(nn) in both time and space. So, if you had a 3x3 square matrix, there would be 33 = 27 iterations and stored array elements. For 4x4, you'd have 44 = 256. You get the idea. The generator can be improved to be O(1) in space, but being that it's a depth-first algorithm, it'll always be O(nn) in time.
此外，根据实现，该算法会在找到 first 解决方案时停止.轻而易举的修改将使您能够找到 all 个解决方案.这个难题的一个有趣的补充是找到具有最小旋转的解决方案.
Also, as implemented, the algorithm stops when it finds the first solution. A trivial modification would allow you to find all solutions. An interesting addition to this puzzle would be to find the solution with the fewest rotations.
这篇关于如何在php中找到多维数组排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
