How to modify de bruijn algorithm for large numbers?-CodePudding

I have the following code for de Bruijn sequence output. It works correctly for small numbers, but if number = 18 it throws an error:

RecursionError: maximum recursion depth exceeded in comparison

I understand what this is connected with, how can I write a dfs function here without recursion?

seen = set()
edges = []

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  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  = A[edges[i]]
    s  = start_node
    return s


n = 18
k = 3
A = '012'
print(de_bruijn(n ,k, A))

CodePudding user response：

Getting past the recursion limit won't let you do too many more of these because the problem will run out of memory, but you have to turn everything into an explicit stack. Here is your code:

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)

Now the idea is that we'll have an action. Which will have a type and value. The types are entering or exiting the function and the loop. Each action will do some code. So the new function will have the following structure:

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':
            ...

And now what do we do in each section? Here is working code that shows the idea. Note that the first thing we put on the stack is the thing we will do second. So we always have to put exit in before enter.

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:]))

BTW a performance tip. Building a large string by appending to it takes time O(n^2). It is much faster to build a large array and then join it.

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)