如何修改大数的 de bruijn 算法？

超过递归限制不会让你做太多这样的事，因为问题会耗尽内存，但你必须把所有东西都变成一个显式的堆栈。这是您的代码：

def dfs(node, k, A):
    for i in range(k):
        str = node + A[i]
        if (str not in seen):
            seen.add(str)
            dfs(str[1:], k, A)
            edges.append(i)

现在的想法是，我们将有一个行动。它将具有类型和值。类型正在进入或退出函数和循环。每个操作都会执行一些代码。因此，新函数将具有以下结构：

def dfs (node, k, A):
    stack = [('enter_function`, (node, k, A))]
    while 0 < len(stack)
        type, value = stack.pop()
        if type == 'enter_function':
            ...
        elif type == 'exit_function':
            ...
        elif type == 'enter_loop':
            ...
        elif type == 'exit_loop':
            ...

现在我们在每个部分做什么？这是显示这个想法的工作代码。请注意，我们放在堆栈上的第一件事是第二件事。因此，我们总是必须在进入之前先设置出口。

def dfs (node, k, A):
    stack = [('enter_function', node)]
    i = 0
    while 0 < len(stack):
        #print(stack)
        action, value = stack.pop()
        if action == 'enter_function':
            node = value
            for i in range(k-1, -1, -1):
                 stack.append(('enter_loop', i))
        elif action == 'exit_function':
            (node, i) = value
            edges.append(i)
        elif action == 'enter_loop':
            i = value
            string = node + A[i]
            if string not in seen:
                seen.add(string)
                stack.append(('exit_function', (node, i)))
                stack.append(('enter_function', string[1:]))

顺便说一句，性能提示。通过附加来构建一个大字符串需要时间。构建一个大型数组，然后加入它要快得多。O(n^2)

def de_bruijn(n, k, A):
    seen.clear()
    edges.clear()

    start_node = A[0] * (n - 1)
    dfs(start_node, k, A)
    s = []
    l = int(math.pow(k, n))
    for i in range(l):
        s.append(A[edges[i]])
    s.append(start_node)
    return "".join(s)