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

[acr0ss]

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

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

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

没有思路，请教诸君。

[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 序列吗？