生成数字随机“模式锁定”序列
问题描述:
今天我的朋友提出,我仍然解决不了的挑战:数字被安排为拨号盘/模式“生成在PHP中的随机数字序列”生成数字随机“模式锁定”序列
-lock即由3行1-9键和3列:
---------------------------
| |
| 1 2 3 |
| |
| 4 5 6 |
| |
| 7 8 9 |
| |
---------------------------
现在,给定的长度,我们要生成的设置长度的数字的随机的,非重复的序列,使用这些标准:
-
甲生成的序列应该按照特定的方向/图案仅通过相邻数字去(可能对角),例如(长度:8),12569874:从第一行
1 2 4 5 6 7 8 9
位数应该永远不会被随后是从第三行开始,反之亦然。列也是如此。例如,一个1不能被随后是8和6不能跟一个4.
可以猜测多个准则可以很容易地从机器人图案锁定系统
下面是产生一些示例对于长度为9的序列:5分之12369874,142536987等,以及用于长度= 6:987532等
我试图与rand()
做到这一点:
$chars = "123456789";
$length = 9;
$clen = strlen($chars)-1;
$id = '';
for ($i = 0; $i < $length; $i++) {
$id .= $chars[mt_rand(0,$clen)];
}
return ($id);
但是,仍然没有运气...
我该如何解决这个问题?
答
有一些限制,但这是你的工作。当我得到报酬时,我只处理头痛:)。
<pre>
<?php
// Keypad
$grid = [
['1', '2', '3'],
['4', '5', '6'],
['7', '8', '9'],
];
// Sequence Target Length
$target_length = 5;
// Place to store the Keypad sequence
$points = [];
// Starting Point
$x = rand(0, 2);
$y = rand(0, 2);
// Run through the process until we have the sequence at the desired length
while (count($points) < $target_length):
// Check if the grid keypad entry has been used
if ($grid[$x][$y]):
// Hasn't been used, so stire it
$points[] = $grid[$x][$y];
// Mark it used
$grid[$x][$y] = NULL;
endif;
// Sanity Check, imagine if you will,.... target length of 9, and you hit 6 5 2 1, You'll vault off into the twilight zone without this
if ((!$grid[$x + 1][$y]) && (!$grid[$x][$y + 1]) && (!$grid[$x - 1][$y]) && (!$grid[$x][$y - 1])):
// We have no where to go
break;
endif;
// Start looking for possible values
do {
$test_x = $x;
$test_y = $y;
$dir = rand(0, 3);
switch ($dir):
case (0):
$test_y--; // Up
break;
case (1):
$test_x++; // Right
break;
case (2):
$test_y++; // Down
break;
case (3):
$test_x--; // Left
break;
endswitch;
// Optional Gibberish
echo "Moving from {$x}, {$y} to {$test_x}, {$test_y} --> " . (($grid[$test_x][$test_y] === NULL) ? 'FAILED' : 'OK!') . '<br>';
// Keep going until we find a valid direction
} while ($grid[$test_x][$test_y] === NULL);
// assign the new coords
$x = $test_x;
$y = $test_y;
// repeat
endwhile;
// report
echo implode('-', $points) . "\n";
?>
</pre>
答
下面是伪代码为基质的例子是这样的:
1 2
3 4
# Get which other numbers are "legal moves" from each number.
adjacency = {
1: [2, 3],
2: [1, 4],
3: [1, 4],
4: [2, 3]
}
# Get the length of code required.
n = 8
# Start at a random position;
pos = rand(keys(adjacency))
result = []
while (n > 0)
n -= 1
newpos = rand(adjacency[pos])
result[] = newpos
pos = newpos
print(result.join(', '))
如果你的矩阵将是大的或将要改变你可能想要写一些代码来生成adjaceny
而不是硬编码它。
答
这里是将应用这些规则的解决方案:
- 路径只能步骤对相邻小区,即是相邻的,其中包括对角
- 一个路径不能包含相同的细胞两次
以下算法对添加到序列的每个数字都使用递归。每当序列“卡住”时,就会发生回溯,并尝试替代路径。如果没有更多替代品可用,则会继续进行追溯。
这是保证返回给定长度的路径,只要给定长度在1-9之间:
function randomSequence($len) {
if ($len < 1 || $len > 9) return []; // No results
$row = [null, 1, 1, 1, 2, 2, 2, 3, 3, 3];
$col = [null, 1, 2, 3, 1, 2, 3, 1, 2, 3];
$neighbors = [[], [2, 4, 5], [1, 4, 5, 6, 3], [2, 5, 6],
[1, 2, 5, 7, 8], [1, 2, 3, 4, 6, 7, 8, 9], [2, 3, 5, 8, 9],
[4, 5, 8], [4, 5, 6, 7, 9], [5, 6, 8]];
// Shuffle the neighbor lists to implement the randomness:
foreach ($neighbors as &$nodes) shuffle($nodes);
$recurse = function ($seq) use (&$len, &$row, &$col, &$neighbors, &$recurse) {
if (count($seq) >= $len) return $seq; // found solution
$last = end($seq);
echo "try " . json_encode(array_keys($seq)) . "\n";
foreach ($neighbors[$last] as $next) {
if (isset($seq[$next])) continue; // Skip if digit already used
$result = $recurse($seq + [$next => $next]);
if (is_array($result)) return $result;
}
};
$choice = rand(1, 9);
return array_keys($recurse([$choice => $choice]));
}
echo "result: " . json_encode(randomSequence(9)) . "\n";
看到它在repl.it
运行,你能解释一下你的条件比较好? – Manav
听起来就像你在考虑标准,然后应该首先尝试它,以暴力方式。通过任何方式获得你正在寻找的结果(无论是多圈还是块大声笑)。你应该可以做到。只要保持循环,直到所有规则匹配。 – IncredibleHat
@Manav:谢谢4回复,请检查更新的问题 –