De Bruijn Sequence

释义 Definition

德布鲁因序列：在给定字母表（如 {0,1}）上构造的一种循环序列，使得所有长度为 n 的可能字符串都恰好出现一次作为连续子串（通常按循环方式理解）。常用于组合数学、编码、密码学与算法设计。（也常写作 de Bruijn sequence）

发音 Pronunciation (IPA)

/də ˈbrɔɪn ˈsiːkwəns/

例句 Examples

A de Bruijn sequence for binary digits can contain every 3-bit pattern exactly once.
一个用于二进制数字的德布鲁因序列可以让每一种 3 位模式都恰好出现一次。

By using a de Bruijn sequence, the test suite covers all length‑n input combinations with minimal repetition, which improves efficiency in automated verification.
使用德布鲁因序列可以以最少的重复覆盖所有长度为 n 的输入组合，从而提高自动化验证的效率。

词源 Etymology

该术语来源于荷兰数学家 Nicolaas Govert de Bruijn（尼古拉斯·戈维特·德布鲁因） 的姓氏；他在组合数学与相关序列的研究中作出重要贡献，因此这种序列以他命名。

相关词 Related Words

• Algorithm
• Combinatorics
• Cycle
• Graph
• Hamiltonian
• Sequence
• Substring

文学与名著中的用例 Literary Works

• The Art of Computer Programming, Volume 4A — Donald E. Knuth（讨论组合生成与相关序列时提及德布鲁因序列）
• A Course in Combinatorics — J. H. van Lint & R. M. Wilson（组合数学教材中涉及德布鲁因序列/德布鲁因图）
• Combinatorics on Words — M. Lothaire（词与序列的组合理论中讨论与之相关的结构）
• Combinatorial Algorithms: Generation, Enumeration, and Search — Donald L. Kreher & Douglas R. Stinson（算法生成与枚举章节中常出现该概念）