[请教] 生活中的算法题：密码尝试次数

[acr0ss]

最近想到一个算法题，和生活有关的。

出租屋最近换了密码锁，6 位密码。实际操作中，在密码前后输入多位其他数字，也能验证成功。既 prefix + password + suffix 的输入，也能解锁。

那么问题来了，6 位密码最多输入多少次能破解？ 假设密码锁的判断方式是最近输入的 12 位字符，既 length(prefix + password + suffix) = 12

没有思路，请教诸君。

题意没有表达清楚，应该是：最多试多少次一定破解。

在换种方式描述一下问题。

一次输入 12 位，可以拆分位 7 个连续的 6 位密码，即分别为 1-6 ，2-7 ，3-8……7-12 位。意味着能同时验证 7 个密码。

有没有一种算法，能够计算出，最少尝试多少次 12 位密码，就一定能试出密码。

算法问题抽象：

十二位数字用字符串形式表示为：000000000000-999999999999 。六位数用字符串形式表示为：000000-999999 。
一个十二位数字可以拆分为七个六位数，例如 12345789012 拆分为 123456, 234567, 345678, 456789, 567890, 678901, 789012 七个六位数，即一个十二位数包含七个六位数。

请问，最少需要多少个十二位数字，包含所有 000000-999999 的六位数。

[nerkeler]

所有排列的情况减去 六位正确密码在十二位从头滑动到末尾的情况？

[acr0ss]

@nerkeler 我题意没说清，应该是最多试多少次一定破解。 你这算法肯定超过 6 位密码 10^6 上界了。

[nuk]

假设是 12 位密码，然后容许的 12 位密码有 10 的 6 次方*6 个，基本上就是试 6 次密码的 1/6 ，就是 1/10^5 几率

[acr0ss]

@nuk 我是算次数，不是概率。而且你这算法很奇怪，逻辑很跳跃不知道是什么的概率。

[smdbh]

感觉是，大概在 1/6 * 10^6 多一点

[acr0ss]

@smdbh 有什么思路吗？ brutal force 也行

[smdbh]

@smdbh 12 位数字，一次可以试 0-6 ，1-7 ，2-8 ，。。。7-12 ，7 个密码，试过的就 hash 查表标记。但这个排列是有相关性的，到后面可能会有重复的，一次查不满 7 个

[acr0ss]

@smdbh 如果要暴力枚举，计算量是 10**12 ，这个机器扛不住。而且类似贪心，不一定是最少的次数（最优解）。

[TongNianShanHe]

感觉好像 leetcode 752

[acr0ss]

@TongNianShanHe 谢谢回复，看了题目，不一样但有启发。可以用广度优先来做，但是时间复杂度数量级是 10**12 ，约等于不行。

[acr0ss]

@acr0ss 又想了一下，bfs/dfs 的初始状态没法确定，visited 数组得按路径维护，内存消耗太大。

[NoOneNoBody]

只要直接输入密码也能打开，就意味着真密码前后的几位，对防暴力破解是没有意义的，它只是对于写下来，即使被别人看到了，也难以猜到而已
例如真密码是六个 0 ，000000+六个任意数字能打开不？能打开的话，那第一次就成功了，意味着最大次数就只和真密码有关

[geelaw]

你需要搜索的是 de Brujin 序列 (sequence)

[jjyy1008]

@NoOneNoBody 这才是正解！楼上的钻书里去了？门禁密码锁设置前缀和后缀的目的就是为了防偷窥用的，哪怕背后有人瞟到了一部分真正密码或者全部真正密码，你接着瞎按一串再确认，这样对防人肉破解很有效。

[huibosa]

如果想自己编程实现这种机制该怎么做呢，比如强制服务端只存储密码的哈希，如果想达到最优性能需要用到哪些算法呢（当然题主讨论的密码锁应该用的不是这种方式）

[xuhai951753]

function recur(pre, times) {
const cur = times === 0 ? 1 / (9 ** 6) : (1 - pre) / 9;

return times < 6 ? (cur + recur(cur, times + 1)) : cur;
}

recur(0, 0);

[acr0ss]

@NoOneNoBody 按我的体重描述，“000000+六个任意数字”可以打开，对应位 len(prefix)=0, (suffix)=6 。如果知道真密码，那一次就行。我只是借着这个场景，实际想要表达的问题是：需要多少个 12 位，就能穷举 6 位数的所有可能。

[acr0ss]

@xuhai951753 不理解，能否解释一下？问题是求次数，但为什么结果是一个小 1 的小数？

[acr0ss]

@jjyy1008 不知道可以不回答，不用趾高气扬、指手划脚。

[NoOneNoBody]

@acr0ss #17
不用想那么多，假设身旁没有人，你会前面多按几个无用的数字么？你只会按 6 位，所以密码就是前 6 位匹配
别人来暴力破解，也是前 6 位对了就可以了

所以，决定因素就是对方是否知道密码为 6 位，知道的话，他也不会那么傻试第 7 位，如果不知道，只能硬着头皮输入 12 位的话，那就是穷举到“密码+000000”的位置结束，按这个思路解
如果已经知道 12 个数字，不知道顺序，就是这 12 个数字的组合，按某个顺序把其结果排序，第一个出现前六位匹配的位置结束
如果知道 12 个数字，且知道顺序，那就更简单了，每次错误去掉第一个数，到成功时，最多应该仅仅只是 prefix 的长度而已，所以，这说明无论多少位，还是不要让别人知道顺序为好，这是最重要的

从上面几点看，穷举后排序的方式是很重要的，它影响了到达“前六位匹配”的距离，从电脑角度看都是 0-->9 正序，但实际意义上这个排序方式是不定的，所以就看题面“最多”是怎么理解了，它是表示求最短距离，还是求正序穷举个数，还是有区别的，“中文博大精深”

[acr0ss]

@NoOneNoBody 介于我“最多最少”表述不明确，且你总是沉浸在密码场景，我已经将问题抽象为算法描述，作为第三条文章附言。

我仔细看了你的回复，你加了预设条件，和我探究的算法问题不同。

[NoOneNoBody]

@acr0ss #20
好吧，我直接给你结果就是，你六位密码是多少，就是多少次
假设你的密码是 123456 ，结果就是 123456+1 次

000000000000 开门失败
000000000001 开门失败
...
000000123455 开门失败
000000123456 开门成功

这个过程就是 123456 次，再加上 12 个 0 一次
这样能明白么？还是我理解错了题意？

[TongNianShanHe]

@acr0ss 我的锅，我没有阐明“只需要猜六位数”的前提条件，昨天就是因为想到了这个前提条件，才会想到这道题的（上面也有老哥提出来了）

[TongNianShanHe]

@NoOneNoBody 本质没错，他的意思是密码前后加无意义数字，其实只需要把前面六个 0 的三个 0 ，移动到最后就行了

[TongNianShanHe]

@NoOneNoBody @acr0ss 哦，我重新看了一下补充，当我没说，如果我没理解错的话，这个可以用滑动窗口？还有楼上说的 de Brujin 序列？（其他其他大佬的解答）

[yw9381]

我理解你这个要表达的是
想要完全包含所有的 6 位数。最少需要多少个 12 位数才可以做到
最差情况为不复用任何数字。即一个 12 位当成两个 6 位。也就是需要 50w 个
最优情况应该就是尽可能的复用数字。算法这块我不太懂。但感觉应该可以把尝试次数压到 10w 以内

[acr0ss]

@NoOneNoBody 老哥我都抽象成纯算法问题了，咋还揪着密码不放呢！？

题意是用十二位表示所有六位数，所有六位数，所有六位数。

[acr0ss]

@yw9381 是的，就是想表达这个问题。
首先想到的上界肯定是 50W ，但也肯定能往下缩减。
由于一个十二位能表示七个六位，所以下界肯定是 10**6 / 7 ，当然这个应该是达不到的。

究竟怎么求具体值，我没有算法思路，就连暴力算法也没思路。

[acr0ss]

@geelaw 看了简介，拙笨无法应用于此问题，烦请指教。

[geelaw]

@geelaw #13
@acr0ss #29

de Bruijn 序列 B(k, n) 的定义是 { 0, 1, ..., k-1 } 的有限序列 X = X[1]X[2] ... X[L] 使 L >= n 且所有 { 0, 1, ..., k-1 }^n 的元素都在 X' = X[1] X[2] ... X[L] X[1] X[2] ... X[n-1] 恰好作为子串出现一次。已经知道 B(k, n) 的长度是 L = k^n ，注意 X ' 长度为 n 的子串恰好有 L = k^n 个，且 { 0, 1, ..., k-1 }^n 恰好就有 k^n 个元素。

在你的情况里 k=10, n=6 ，但 de Bruijn 序列并不是你直接要的答案，不过已经非常接近了。

你希望寻找一系列长度是 12 的串 Y(1), ..., Y(z) 使得诸 Y(i) 的所有长度为 6 的子串覆盖了 { 0, ..., 9 }^6 ，很明显 z >= ceiling(10^6/7) = 142858 ，而取

Y(i) = X'[7(i-1)+1] ... X[7(i-1)+12]
1 <= i <= 142857
Y(142858) = X'[7(142858-1)+1 = 10^6] ... X'[10^6+(10-1)] 0 0

则诸 Y(i) 的所有长度为 6 的子串当然就包括了 X' 所有长度为 6 的子串，后者就是所有长度为 6 的串。这说明需要的 z 可以是 142858 。

暂且称上面长度为 12 的串是“窗口”。类似地，可以算出密码字符有 k 个，密码长度是 n ，窗口长度是 m 的时候需要的最小的窗口数就是 ceiling(k^n/m)。

计算最小窗口数和计算这一系列窗口是两回事儿，不过后者也不难，de Bruijn 序列有算法可以生成，再练习一下使用搜索引擎的能力就好。

[geelaw]

@geelaw #30 Ugh, 应该是 ceiling(k^n/(m-n+1)).

[NoOneNoBody]

好吧，是我读错题了
12 个抽取连续 6 个连续的，只有 7 种可能，每种可能都能满足一个 10**6
10**6/7≈142857.14285714287

[acr0ss]

@geelaw 多谢老哥指点，数学真是奇妙，没想道这个问题已经有答案了。
我还有一个问题： 能确保对于任意 n,k 和窗口 m ，都存在对应的 de bruijn 序列吗？