De Bruijn sequence | Set 1 | Javascript 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
var seen = new Set ( ) ; var edges = [ ] ; function dfs ( node , k , A ) { for ( var i = 0 ; i < k ; ++ i ) { var str = node + A [ i ] ; if ( ! seen . has ( str ) ) { seen . add ( str ) ; dfs ( str . substring ( 1 ) , k , A ) ; edges . push ( i ) ; } } } function deBruijn ( n , k , A ) { seen = new Set ( ) ; edges = [ ] ; var startingNode = A [ 0 ] . repeat ( n - 1 ) ; dfs ( startingNode , k , A ) ; var S = " " ; var l = Math . pow ( k , n ) ; for ( var i = 0 ; i < l ; ++ i ) S += A [ edges [ i ] ] ; S += startingNode ; return S ; } function strings ( n , charAt ) { var str = " " ; for ( var i = 0 ; i < n ; i ++ ) str += charAt ; return str ; } var n = 3 , k = 2 ; var A = " " ; document . write ( deBruijn ( n , k , A ) ) ;