Attempt at generating debruijn sequences from traversing debruijn graphs.

debruijn-graph.js

// http://web.mnstate.edu/goytadam/talks/DBS.pdf
const SIZE = 8

const vertices = getEveryBitPermutation(SIZE).reduce((m, x) => {
  m.set(x.toString(2).padStart(SIZE, 0), new Array)
  return m
}, new Map)

for (let [v, edges] of vertices) {
  for (let [v2] of vertices) {
    if (v != v2 && isWired(v, v2)) {
      edges.push(v2)
    }
  }
  // const l = rol(parseInt(v, 2), SIZE).toString(2).padStart(SIZE, 0)
  // const r = ror(parseInt(v, 2), SIZE).toString(2).padStart(SIZE, 0)

  // if (l !== v) {
  //   edges.push(l)
  //   // vertices.get(l).push(v)
  // }
  // if (r !== v) {
  //   edges.push(r)
  //   // vertices.get(r).push(v)
  // }

  // console.log(`${v} => ${edges.join(':')}`)
}

function isWired(a, b) {
  // return a[a.length - 1] === b[0]
  let a_end = a.split('')
  a_end.shift()
  a_end = a_end.join('')
  let b_start = b.split('')
  // b_start.pop()
  b_start.pop()
  b_start = b_start.join('')
  return a_end === b_start
}

let i = 1
for (let string of collectStrings(vertices)) {
  // if (isDeBruijnSequence(string, SIZE))
    console.log(String(i++).padStart(4, ' '),
      isDeBruijnSequence(string, SIZE) ? '!' :' ',
      string,
      parseInt(string, 2).toString(16)
    )
}

function *collectStrings(vertices) {
  const visited = new Uint32Array(2 ** SIZE)
  for (let [v] of vertices) {
    // zero
    for (let i = 0, n = visited.length; i < n; i++) {
      visited[i] = 0
    }
    const string = dfs(v, vertices, visited, 1).join('')
    if (string) yield string
  }
}

function dfs(start, vertices, visited, dir, results = []) {
  const stack = [start]
  visited[parseInt(start, 2)] = 1
  let i = 0
  while (stack.length) {
    const v = stack.pop()

    if (visited[parseInt(v, 2)] != 1) {
      continue
    }
    visited[parseInt(v, 2)] = 1

    const targets = vertices.get(v)

    if (targets.length) {
      targets.forEach(handleTarget)

      function handleTarget(target) {
        const key = parseInt(target, 2)
        if (results.length === 0) {
          let t = target.split('')
          t.pop()
          results.push(t.join(''))
        } else {
          let t = target.split('')
          //

          results.push(t.shift(''))
        }
        if (visited[key] != 1) {
          stack.push(target)
        }
      }
    }
  }

  return results
}

function getEveryBitPermutation(size) {
  let start = 0
  let end = 2 ** size
  const set = new Uint32Array(end - start)
  let i = 0
  while (start < end) {
    set[i++] = start++
  }
  return set
}

function rol(n, size) {
  const bits = n.toString(2).padStart(size, 0).split('').reverse()
  const left = bits.pop()
  bits.unshift(left)
  const string = bits.reverse().join('')
  const number = parseInt(string, 2)
  return number
}

function ror(n, size) {
  const bits = n.toString(2).padStart(size, 0).split('').reverse()
  const right = bits.shift()
  bits.push(right)
  const string = bits.reverse().join('')
  const number = parseInt(string, 2)
  return number
}

function isDeBruijnSequence(string, spanSizeInBits) {
  let bits = string.split('').reverse()
  let i = 0
  const totalElementSize = 2 ** spanSizeInBits
  const chunksVisited = new Uint8ClampedArray(totalElementSize)
  while (i < bits.length) {
    const chunk = bits.slice(i, i + spanSizeInBits)
    if (chunk.length < spanSizeInBits) {
      const diff = bits.slice(0, spanSizeInBits - chunk.length)
      chunk.push(...diff)
    }
    const string = chunk.reverse().join('')
    const number = parseInt(string, 2)
    if (chunksVisited[number] == 1) {
      return false
    }
    chunksVisited[number] = 1
    i++
  }
  return true
}

// https://www.geeksforgeeks.org/de-bruijn-sequence-set-1/

Initial output:

0000000101000000 false
0000001111000000 false
0000010101000001 false
0000011111000001 true
0000100101000010 true
0000101111000010 true
0000110101000011 false
0000111111000011 false
0001000101000100 true
0001001111000100 true
0001010101000101 false
0001011111000101 true
0001100101000110 true
0001101111000110 true
0001110101000111 false
0001111111000111 false
0010000101001000 true
0010001111001000 true
0010010101001001 false
0010011111001001 false
0010100101001010 false
0010101111001010 true
0010110101001011 false
0010111111001011 false
0011000101001100 true
0011001111001100 true
0011010101001101 false
0011011111001101 true
0011100101001110 true
0011101111001110 true
0011110101001111 false
0011111111001111 false
0100000101010000 false
0100001111010000 true
0100010101010001 false
0100011111010001 true
0100100101010010 false
0100101111010010 false
0100110101010011 false
0100111111010011 false
0101000101010100 false
0101001111010100 true
0101010101010101 false
0101011111010101 false
0101100101010110 false
0101101111010110 true
0101110101010111 false
0101111111010111 false
0110000101011000 false
0110001111011000 true