2

一个在求职面试中被问到的问题（我几乎失败了），可悲的是，我仍然无法弄清楚。

让我们假设给你一个正整数 n。假设您构造了一个仅由 1 和 0 组成的序列，并且您想要构造一个长度为 2^n + n-1 的序列，使得由相邻数字组成的每个长度为 n 的序列都是唯一的。

例如

00110 (00, 01, 11, 10) 对于 n=2

如何构建这样一个序列？

我认为应该从 0000..0 （n 个零）开始，然后做点什么。

如果有一种建设性的方法，也许我可以将该方法扩展到构造一个仅由 0、1、...、k-1 组成的序列，并且长度为 k^n + n-1，这样每个序列由相邻数字组成的长度 n 是唯一的（或者可能不是......）

（对不起，我的 n=3 序列是错误的，所以我删除了它。另外，我从来没有听说过 De Bruijin 的序列。我现在知道了！感谢所有的答案和评论）。

4

1 回答 1

1

这让我觉得这是一个非常雄心勃勃的面试问题；如果你不知道答案，你不可能在几分钟内得到答案。

正如评论中提到的，这实际上只是de Bruijn 序列的推导，只是展开。您可以阅读上面链接的 Wikipedia 文章以获取更多信息，但它提出的算法虽然有效，但并不容易推导出。有一个更简单（但存储更密集）的算法，我认为它是民俗的；至少，我不知道它有什么名字。至少描述起来很简单：

  • n以0开头

  • 越长越好：

    • 如果您可以添加 a1而无需重复以前看到的n-sequence，请这样做。
    • 如果不是，但您可以添加 a0而无需重复先前看到的n-sequence，请这样做。
    • 否则，完成。

这要求您在每次迭代时搜索整个字符串，需要指数时间，或者维护所有可见序列的布尔数组（大概编码为二进制数），需要指数空间。“按字典顺序连接所有 Lyndon 单词”解决方案效率更高，但留下了按字典顺序生成所有 Lyndon 单词的问题。

于 2013-11-14T16:16:35.530 回答