I have this code which I put together for trying to generate all possible de Bruijn sequences, but not getting "expected" results. It uses (what I think are called) de Bruijn graphs, with Eulerian cycles.
const SIZE = 8
const vertices = getEveryBitPermutation(SIZE).reduce((m, x) => {
m.set(x, new Array)
return m
}, new Map)
for (let [v, edges] of vertices) {
const l = rol(v, SIZE)//.toString(2).padStart(SIZE, 0)
const r = ror(v, SIZE)//.toString(2).padStart(SIZE, 0)
edges.push(l)
edges.push(r)
}
for (let string of collectStrings(vertices)) {
if (isDeBruijnSequence(string, SIZE))
console.log(string, parseInt(string, 2).toString(16))
}
function *collectStrings(vertices) {
const strings = {}
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).join('')
yield string
strings[string] = true
}
return Object.keys(strings).sort()
}
function dfs(start, vertices, visited, results = []) {
const stack = [start]
while (stack.length) {
const v = stack.shift()
visited[v] = 1
const targets = vertices.get(v)
if (targets) {
targets.forEach(target => {
if (visited[target] != 1) {
visited[target] = 1
results.push(target.toString(2).padStart(SIZE, 0))
stack.push(target)
}
})
}
}
return results
}
function getEveryBitPermutation(size) {
let start = 2 ** (size - 1)
let end = 2 ** size - 1
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
}First of all, there is a SIZE property. This tells how many bits there are throughout the program. In this case, 8. So it generates all permutations of 8 bits (vertices), and then rotates left and right to generate two outward edges on each vertex. This creates a basic graph. Then it does DFS on this graph to generate walks I guess, and then outputs a string starting from each vertex. There is a function isDeBruijnSequence which checks if it's a de Bruijn sequence as well.
I am only getting a small handful (5-20 depending on SIZE) out of the possible hundreds of strings generated that turn out to be de Bruijn sequences. I am also not sure if I should be doing something else to get this right.
One final thing I am not sure about is how I distinguish between n. In my case, taking 8 bits as an example, since there are two edges, this means every 8-bit vertex will result in a 16-bit result. At least that's what it seems like it's doing. So wondering how I can correct this to generate all possible de Bruijn sequences, for any SIZE?
Another code revision and results seem to be getting slightly better.
This talk/presentation seems say you can generate all the de Bruijn sequences from a graph in some sort of way, but I have seen a few different ways of structuring the edges and such, so not sure what the "correct" approach is or if I have it somewhat right.