algorithm - 需要帮助建立高效的穷举搜索算法

Question

有 10 个按钮。如果按正确顺序按下这些按钮(按顺序按下 5 次)，这些按钮可以解锁。每次按下按钮都会触发解锁检查。

示例:“密码”是 123456，我按下按钮 0 1 2 3 4 5 6 我从第 6 次按下按钮开始解锁。

我需要设计算法以最有效的方式尝试所有可能的组合(即应按下最少数量的按钮)。

我可以将按钮编号解释为数字，将按顺序按下的按钮数解释为数字位置，然后尝试所有 99999 组合以尝试解锁锁，但我觉得有一种更有效的算法可以做到这一点。

我可以做些什么来优化这个搜索吗？

Answer 1

要优化对锁的暴力攻击，您可以使用 De Bruijn sequences .

The sequence can be used to shorten a brute-force attack on a PIN-like code lock that does not have an "enter" key and accepts the last n digits entered. For example, a digital door lock with a 4-digit code would have B(10, 4) solutions, with length 10,000. Therefore, only at most 10,000 + 3 = 10,003 (as the solutions are cyclic) presses are needed to open the lock. Trying all codes separately would require 4 × 10,000 = 40,000 presses.