生成随机的数字"图案密码"序列

Question

今天我的朋友提出了一个挑战，我仍然无法解决：“用PHP生成随机数字序列”

这些数字排列成拨号键盘/图案锁，由3行3列的1-9个数字键组成：

 ---------------------------
|                           |
|     1       2      3      |
|                           |
|     4       5      6      |
|                           |
|     7       8      9      |
|                           |
 ---------------------------

现在，我们需要生成一个指定长度的随机、不重复数字序列，需要遵守以下规则：

1. 序列中的数字不能重复

2. 生成的数字序列必须是随机的

3. 数字序列的长度由参数指定

1. A generated sequence should follow a specific direction/pattern going only via neighboring digits (possibly diagonally), for example (length:8), 12569874:

    1  2
         
    4    5  6
            
    7  8  9 
   

2. Digits from the first row should never be followed by a digit from the third row, and vice-versa. The same goes for columns. For example a 1 cannot be followed by a 8, and a 6 cannot be followed by a 4.

3. can guess more criteria can easily from android pattern-lock system

以下是关于长度为9的示例生成序列：12369874/5、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);

但是，仍然没有运气...

我该如何解决这个问题？

- Anu Tig3r

---

你能更好地解释你的标准吗？ - Manav

@trincot：只允许穿越到相邻的上下行，例如1 -> 5 -> 2 -> 4是有效的，但1|2|3 -> 7|8|9或9|8|7 -> 1|2|3是不允许的，因为它们穿过了中间一行。 - Anu Tig3r

4 -> 3，穿过中间列？这样可以吗？ - trincot

也许我误解了第二条规则？这是否意味着如果你有1-2，那么它不能跟随3，如果你有7-8，它也不能跟随9？这是我理解的，但也许这是关于其他事情？ - trincot

@trincot：规则2提到，它应该遵循一个特定的顺序，不能回头，这意味着，如果8后面是9，那么9就不能跟在7后面（8->9->7是错误的，4->1->7也是错误的，6->9->3也是错误的）。 - Anu Tig3r

Answer 1

它有一些限制，但这需要您自己解决。当我得到报酬时，我只处理头痛问题 :）。

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

- Wranorn

---

你真是太棒了...非常感谢，亲爱的，你是无价之宝 :) 所以我付不起你 ;) - Anu Tig3r

很高兴能够帮忙！（开玩笑，我只是为了乐趣编程，不需要支付任何费用 :) ） - Wranorn

这似乎允许生成1-2-3，并且从未产生垂直或水平邻居以外的其他移动。此外，当target_length = 9时，结果经常不完整。 - trincot

给我看一下OP提到了斜向移动的地方，我会进行调整。target_length = 9实际上是“尽可能长时间运行”。这是一个小网格和概念验证，细节由OP解决。个人而言，如果我需要，我会选择一个基于36的网格（6x6 0-9A-Z），并且也从中心开始（尽可能）。但再次强调，这不是他要求的。 - Wranorn

@trincot：是的，有时候Wranorn的解决方案不能根据确切长度产生有效的输出，但它总是像魔法一样奏效。 - Anu Tig3r

@trincot 我给你的解决方案点了赞，它更加全面。 - Wranorn

Answer 2

以下是一个应用这些规则的解决方案：

• 路径只能向相邻的单元格前进，包括对角线相邻
• 路径不能包含同一单元格两次

以下算法使用递归添加每个数字到序列中。当序列“卡住”时，回溯发生，尝试另一条路径。如果没有其他选择，则继续回溯。

保证返回给定长度的路径，只要给定的长度在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上的运行情况。

- trincot

---

现在已经更正了，并且我添加了另一个链接，以防万一。 - trincot

Answer 3

这里是一个伪代码示例，用于描述一个类似于以下矩阵的矩阵：

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(', '))

如果你的矩阵很大或者会变化，你可能想编写一些代码来生成邻接矩阵，而不是硬编码它。

- Thomas David Baker