De Bruijn sequence | Set 1 | Python3 implementation of the above approach ; Modified DFS in which no edge is traversed twice ; Function to find a de Bruijn sequence of order n on k characters ; Clearing global variables ; Number of edges ; Driver code
import math NEW_LINE seen = set ( ) NEW_LINE edges = [ ] NEW_LINE def dfs ( node , k , A ) : NEW_LINE INDENT for i in range ( k ) : NEW_LINE INDENT str = node + A [ i ] NEW_LINE if ( str not in seen ) : NEW_LINE INDENT seen . add ( str ) NEW_LINE dfs ( str [ 1 : ] , k , A ) NEW_LINE edges . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def deBruijn ( n , k , A ) : NEW_LINE INDENT seen . clear ( ) NEW_LINE edges . clear ( ) NEW_LINE startingNode = A [ 0 ] * ( n - 1 ) NEW_LINE dfs ( startingNode , k , A ) NEW_LINE S = " " NEW_LINE l = int ( math . pow ( k , n ) ) NEW_LINE for i in range ( l ) : NEW_LINE INDENT S += A [ edges [ i ] ] NEW_LINE DEDENT S += startingNode NEW_LINE return S NEW_LINE DEDENT n = 3 NEW_LINE k = 2 NEW_LINE A = "01" NEW_LINE print ( deBruijn ( n , k , A ) ) NEW_LINE