#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/de-bruijn-sequence-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/de-bruijn-sequence-implementation

Repovive

De Bruijn Sequence - Implementation - Euler Paths and Circuits | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

De Bruijn Sequence - Implementation

Code walkthrough.

function deBruijn(n):
    if n == 1:
        return "01"

    // Build adjacency list
    // Vertex v has edges to 2*v mod 2^(n-1) and (2*v+1) mod 2^(n-1)
    numVertices = 2^(n-1)
    adj = array of lists

    for v from 0 to numVertices - 1:
        adj[v] = [2*v mod numVertices, (2*v + 1) mod numVertices]

        // Hierholzer from vertex 0
        path = hierholzer(adj, 0)

        // Build result: first (n-1) bits of start vertex, then last bit of each edge
        result = binary(path[0], n-1)
        for i from 0 to path.length - 2:
            result = result + str(path[i+1] mod 2)

            return result

This runs in $O(k^n)$ time and uses $O(k^n)$ space.