Click here to see the full article post
In approach #1, the Python code is missing the function name. And this doesn't sound right:
we should expect intuitively that taking any path greedily in some order will probably result in an Euler path. Actually, this intuition is also a theorem: any connected directed graph where all nodes have equal in-degree and out-degree has an Euler circuit
The theorem only says that an Euler circuit exists, not that you'll probably walk one by greedily randomly walking around.
@ManuelP Thanks for the corrections. I will think about how to amend the article to discuss the intuition behind Hierholzer's algorithm, with edits coming later.
Could you please clarify the while loop in the second solution? How does it produce a valid Bruijin sequence?
@dcx9306 Basically we want the cycles of some permutation. The while loop is just finding a cycle and recording the cycle as we proceed. I will explain this better during the rewrite, but basically imagine the permutation is like [0, 3, 1, 2, 4]. We will record the cycles in order: (0) (1 3 2) (4).
The first solution is really confused. I think it is equal to start from 00..0(k-1) using decrease value(eg. k-1, k-2, ... 0) preorder.
@awice Thanks awice! I did write it down. But I don't think it's just simply S'-->S mapping as mentioned in the article. I can't figure out why it's a valid Bruijin sequence. Is there any proof for the soundness? I appreciate it!
Is this a Euler Circuit problem?
We do not need to cover all edges but only all nodes.
Hierholzer's Algorithm goes every edge only once and there are kn edges. (K(n-1) nodes and each node has k out edges)
Shouldn't the time/space complexity be O(k**n) ?
It is a Euler Circuit problem on an (n − 1)-dimensional de Bruijn graph.
So we need to cover all edges, not only all nodes.
In the second approach, why do we need to append zeros at the end of the algorithm?
@ryx for the second solution I think the reason the zeroes are appended is that the de Bruijin sequence allows substrings to wrap around but the safe cracking problem does not.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.