我有以下 de Bruijn 序列輸出代碼。它適用于小數字，但如果 number = 18 則會引發錯誤：
RecursionError: maximum recursion depth exceeded in comparison
我了解這與什么有關，如何在沒有遞回的情況下在這里撰寫 dfs 函式？
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))
uj5u.com熱心網友回復：
超過遞回限制不會讓你做太多這些，因為問題會耗盡記憶體，但你必須把所有東西都變成一個顯式的堆疊。這是您的代碼：
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532366.html
標籤：算法序列深度优先搜索
下一篇：這個演算法的復雜度是多少？