德布鲁因序列（De Bruijn Sequence）是组合数学中的经典问题。给定字母表大小 $k$ 和子串长度 $n$，德布鲁因序列是一个循环序列，其中所有可能的 $k^n$ 个长度为 $n$ 的子串恰好各出现一次。本文用Java实现基于De Bruijn图和Hierholzer算法的序列构造。
问题分析
以二进制字母表 $k=2$、子串长度 $n=3$ 为例，所有可能的长度为3的二进制串共有 $2^3 = 8$ 个：000, 001, 010, 011, 100, 101, 110, 111。对应的德布鲁因序列是一个长度为 $2^3 = 8$ 的循环序列，例如 00010111，循环展开后包含所有8个三元组各一次。
德布鲁因序列的核心性质：
– 长度：恰好为 $k^n$ 个符号
– 循环性：序列首尾相连形成环
– 唯一性：所有 $k^n$ 个长度为 $n$ 的子串各出现恰好一次
算法核心思想
De Bruijn图构造
将每个长度为 $n-1$ 的串作为图中的一个节点。对于节点 $u = a_1a_2…a_{n-1}$，存在一条边指向 $v = a_2a_3…a_{n-1}b$（其中 $b \in {0,1,…,k-1}$），边的标签为 $b$。
Hierholzer算法求欧拉回路
德布鲁因序列的构造等价于在De Bruijn图中寻找一条欧拉回路（经过每条边恰好一次的闭合路径）。Hierholzer算法的步骤：
- 从任意节点出发，沿着未访问的边行走直到回到起点形成环
- 如果环上存在仍有未访问边的节点，从该节点继续扩展
- 将新形成的环合并入原路径
- 重复直到所有边都被访问
Java完整实现
import java.util.*;
/**
* 德布鲁因序列（De Bruijn Sequence）构造器
* 基于De Bruijn图和Hierholzer欧拉回路算法
*/
public class DeBruijnSequence {
/**
* 使用Hierholzer算法构造德布鲁因序列（二进制版本）
* @param n 子串长度
* @return 德布鲁因序列字符串
*/
public static String constructBinary(int n) {
if (n == 1) {
return "01";
}
// 节点数为 2^(n-1)，边数为 2^n
int numNodes = 1 << (n - 1);
// 邻接表：每个节点有两条出边（标记0和1）
// 用栈来模拟Hierholzer算法
StringBuilder sequence = new StringBuilder();
Deque<Integer> stack = new ArrayDeque<>();
boolean[] visited = new boolean[1 << n]; // 标记每条边是否被访问
// 从节点0开始（即n-1个0组成的串）
stack.push(0);
while (!stack.isEmpty()) {
int node = stack.peek();
// 尝试走边0和边1
boolean hasUnvisited = false;
for (int bit = 0; bit <= 1; bit++) {
// 边的唯一标识：当前节点 * 2 + bit
int edgeId = (node << 1) | bit;
if (!visited[edgeId]) {
visited[edgeId] = true;
// 下一个节点：去掉最高位，保留n-1位
int nextNode = edgeId & ((1 << (n - 1)) - 1);
stack.push(nextNode);
hasUnvisited = true;
break;
}
}
if (!hasUnvisited) {
// 当前节点没有未访问的边，回溯并记录
stack.pop();
if (!stack.isEmpty()) {
// 记录从当前节点到栈顶节点的转移位
int prevNode = stack.peek();
// 判断是通过0还是1边到达的
int edgeId = (prevNode << 1);
if ((edgeId & ((1 << (n - 1)) - 1)) == node) {
sequence.append('0');
} else {
sequence.append('1');
}
}
}
}
// 上面的方法有点复杂，换用更清晰的递归版本
return constructBinaryRecursive(n);
}
/**
* 更清晰的递归实现：基于Hierholzer算法
*/
public static String constructBinaryRecursive(int n) {
if (n == 1) {
return "01";
}
Set<Integer> visitedEdges = new HashSet<>();
StringBuilder result = new StringBuilder();
// Hierholzer DFS
hierholzer(0, n, visitedEdges, result);
// 结果需要反转，并补充前n-1个0
return result.reverse().toString() + "0".repeat(n - 1);
}
private static void hierholzer(int node, int n, Set<Integer> visited, StringBuilder result) {
for (int bit = 0; bit <= 1; bit++) {
int edge = (node << 1) | bit;
if (!visited.contains(edge)) {
visited.add(edge);
int nextNode = edge & ((1 << (n - 1)) - 1);
hierholzer(nextNode, n, visited, result);
result.append(bit);
}
}
}
/**
* 通用k进制德布鲁因序列构造
* @param k 字母表大小
* @param n 子串长度
* @return 德布鲁因序列（用0-k-1的数字表示）
*/
public static int[] constructGeneral(int k, int n) {
if (n == 1) {
int[] seq = new int[k];
for (int i = 0; i < k; i++) {
seq[i] = i;
}
return seq;
}
int numEdges = (int) Math.pow(k, n);
boolean[] visited = new boolean[numEdges];
List<Integer> result = new ArrayList<>();
// 从节点0开始DFS
dfsGeneral(0, k, n, visited, result);
// 反转结果并转换为数组
Collections.reverse(result);
int[] sequence = new int[result.size() + n - 1];
for (int i = 0; i < result.size(); i++) {
sequence[i] = result.get(i);
}
// 补充前n-1个0
for (int i = result.size(); i < sequence.length; i++) {
sequence[i] = 0;
}
return sequence;
}
private static void dfsGeneral(int node, int k, int n, boolean[] visited, List<Integer> result) {
for (int symbol = 0; symbol < k; symbol++) {
int edge = node * k + symbol;
if (!visited[edge]) {
visited[edge] = true;
int nextNode = edge % ((int) Math.pow(k, n - 1));
dfsGeneral(nextNode, k, n, visited, result);
result.add(symbol);
}
}
}
/**
* 验证序列是否为有效的德布鲁因序列
*/
public static boolean validate(String sequence, int k, int n) {
if (sequence == null || sequence.length() != (int) Math.pow(k, n)) {
return false;
}
Set<String> substrings = new HashSet<>();
int len = sequence.length();
for (int i = 0; i < len; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
sb.append(sequence.charAt((i + j) % len));
}
substrings.add(sb.toString());
}
// 检查是否包含所有k^n个子串
return substrings.size() == (int) Math.pow(k, n);
}
/**
* 验证通用版本
*/
public static boolean validate(int[] sequence, int k, int n) {
int expectedLen = (int) Math.pow(k, n);
if (sequence == null || sequence.length != expectedLen) {
return false;
}
Set<String> substrings = new HashSet<>();
int len = sequence.length;
for (int i = 0; i < len; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
int val = sequence[(i + j) % len];
if (val < 0 || val >= k) {
return false;
}
sb.append(val);
}
substrings.add(sb.toString());
}
return substrings.size() == expectedLen;
}
/**
* 打印序列及其所有循环子串
*/
public static void printSequence(String sequence, int n) {
System.out.println("德布鲁因序列: " + sequence);
System.out.println("长度: " + sequence.length());
System.out.println("所有长度为" + n + "的循环子串:");
int len = sequence.length();
for (int i = 0; i < len; i++) {
System.out.print(" [" + i + "] ");
for (int j = 0; j < n; j++) {
System.out.print(sequence.charAt((i + j) % len));
}
System.out.println();
}
}
public static void main(String[] args) {
System.out.println("=== 二进制德布鲁因序列 (n=3) ===");
String seq3 = constructBinaryRecursive(3);
printSequence(seq3, 3);
System.out.println("验证结果: " + (validate(seq3, 2, 3) ? "通过" : "失败"));
System.out.println("\n=== 二进制德布鲁因序列 (n=4) ===");
String seq4 = constructBinaryRecursive(4);
printSequence(seq4, 4);
System.out.println("验证结果: " + (validate(seq4, 2, 4) ? "通过" : "失败"));
System.out.println("\n=== 三进制德布鲁因序列 (k=3, n=2) ===");
int[] seq32 = constructGeneral(3, 2);
System.out.print("序列: ");
for (int val : seq32) {
System.out.print(val);
}
System.out.println();
System.out.println("验证结果: " + (validate(seq32, 3, 2) ? "通过" : "失败"));
}
}
时间复杂度分析
德布鲁因序列构造的核心是De Bruijn图上的欧拉回路遍历：
– 节点数：$k^{n-1}$
– 边数：$k^n$
– 时间复杂度：$O(k^n)$，每条边恰好访问一次
– 空间复杂度：$O(k^n)$，用于标记边访问状态和存储结果
算法应用
德布鲁因序列在计算机科学中有广泛应用：
– 组合锁破解：通过最短的按键序列测试所有可能的密码组合
– 基因组测序：DNA序列拼接中的重叠群组装
– 伪随机数生成：作为最大周期LFSR的反馈多项式输出
– 魔方位表示：高维空间中的格雷码推广
拓展思考
德布鲁因序列的数量恰好为 $(k!)^{k^{n-1}} / k^n$ 个（对于 $k$ 进制、长度 $n$ 的序列），这个结果可以通过计算De Bruijn图中的欧拉回路数得到。
