如何实现这个算法？

Question

有一段时间我试图破解一个发送12位二进制“密钥”的遥控器。

我做的设备可以工作，但速度很慢，因为它每秒只能尝试大约50个组合（4096个代码=49152个位=约16分钟）。

我打开了接收器并发现它正在使用移位寄存器来检查代码，并且在尝试之间不需要延迟。这意味着接收器只是查看最后接收到的12位，以查看它们是否与密钥匹配。

这意味着如果通过流111111111111000000000000发送，它实际上已经尝试了所有这些代码。

111111111111    111111111110    111111111100    111111111000
111111110000    111111100000    111111000000    111110000000
111100000000    111000000000    110000000000    100000000000
000000000000

在这种情况下，我使用了24位来尝试13个12位的组合（>90％的压缩）。

有没有人知道一种算法可以利用这一点来减少我发送的49152位？

- John

Answer 1

你所说的是de Bruijn序列。如果你不关心它是如何工作的，只想要结果，这里就是。

- Pesto

---

绝对太棒了。而且长度为4096位，压缩率达到91.6％，即每12位序列只需1位。非常感谢，你让我的星期五变得美好！ - John

这是一个关于它的有趣故事： http://www.stefangeens.com/2004/10/the-de-bruijn-c.html - compie

在Dota中，Invoker有一个带有三个插槽的法术队列（或者说曾经有，我认为他已经被简化了）。每次你召唤一个球体时，它会将其从开头移动到末尾。该图描述了当前法术相邻的确切路径。虽然在Dota中是三种状态和三个插槽（与图表只有两个字母和三个插槽不同），但你施放的法术由队列的当前状态（即三个球体的排列组合）控制。 - Mark Canlas

Answer 2

就我个人而言，我想翻转每个12位序列中的一个比特位可以解决另外13种组合，例如111111111101000000000010，然后是111111111011000000000100等。但是你仍然需要进行很多排列组合，即使只有一个比特位，我认为你仍然需要做111111111101000000000100等操作。然后在一侧翻转两个比特位和另一侧的1个比特位等。

- Chochos