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.
CodePudding user response：
I figured it out, it has to be a hamiltonian cycle that is traversed.
// import findCycle from 'find-cycle/directed'
import hamiltonianCycle from 'javascript-algorithms-and-data-structures/src/algorithms/graph/hamiltonian-cycle/hamiltonianCycle.js'
import Graph from 'javascript-algorithms-and-data-structures/src/data-structures/graph/Graph.js'
import GraphVertex from 'javascript-algorithms-and-data-structures/src/data-structures/graph/GraphVertex.js'
import GraphEdge from 'javascript-algorithms-and-data-structures/src/data-structures/graph/GraphEdge.js'
const SIZE = 5
const vertices = getEveryBitPermutation(SIZE).reduce((m, x) => {
m[x.toString(2).padStart(SIZE, 0)] = new Array
return m
}, {})
Object.keys(vertices).forEach(v => {
Object.keys(vertices).forEach(v2 => {
if (v != v2 && isWired(v, v2)) {
if (!vertices[v].includes(v2))
vertices[v].push(v2)
}
})
})
function isWired(a, b) {
let a_end = a.split('')
a_end.shift()
a_end = a_end.join('')
let b_start = b.split('')
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)
let j = 0
for (const v in vertices) {
// zero
for (let i = 0, n = visited.length; i < n; i ) {
visited[i] = 0
}
const strings = dfs(j , v, vertices, visited, 1)
for (let string of strings) {
if (string) yield string
}
}
}
function dfs(i, start, vertices, visited, dir, results = []) {
const graph = new Graph(true)
graph.addVertex(new GraphVertex(start))
Object.keys(vertices).forEach(v => {
const vertex = new GraphVertex(v)
try {
graph.addVertex(vertex)
} catch (e) {}
})
Object.keys(vertices).forEach(v => {
const vertex = graph.getVertexByKey(v)
vertices[v].forEach(e => {
graph.addEdge(new GraphEdge(vertex, graph.getVertexByKey(e)))
})
try {
graph.addEdge(new GraphEdge(vertex, graph.getVertexByKey(start)))
} catch (e) {}
})
const cycle = hamiltonianCycle(graph)
while (cycle.length) {
const vertexes = cycle.pop()
const key = []
vertexes.forEach(vert => {
key.push(vert.value[vert.value.length - 1])
})
results.push(key.join(''))
}
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 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
}
Sample output from the stream:
30698 ! 00100011001111101101001010111000 233ed2b8
30699 ! 00100011001111101010010110111000 233ea5b8
30700 ! 00100011001111101001010110111000 233e95b8
30701 ! 00100011001110110101001011111000 233b52f8
30702 ! 00100011001110110100101011111000 233b4af8
30703 ! 00100011001110101001011011111000 233a96f8
30704 ! 00100011001110100101011011111000 233a56f8
30705 ! 00100011001011111011010100111000 232fb538
30706 ! 00100011001011101101010011111000 232ed4f8
30707 ! 00100011001011011111010100111000 232df538
30708 ! 00100011001011011101010011111000 232dd4f8
It takes 1.5 minutes to generate all 65536 de Bruijn sequences for n = 5. For n > 5 it crashes, using too much memory to generate all the hamiltonian cycles.