如何使用 de Bruijn 图生成所有 de Bruijn 序列（JavaScript）？
How to generate all de Bruijn sequences using de Bruijn graphs (in JavaScript)?
我有 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，有欧拉循环。
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
}
首先，有一个SIZE属性。这表明整个程序有多少位。本例中为8。所以它生成8位（顶点）的所有排列，然后左右旋转，在每个顶点上生成两条向外的边。这将创建一个基本图形。然后它在这个图上做 DFS 来生成我猜的行走，然后输出一个从每个顶点开始的字符串。有一个函数 isDeBruijnSequence 可以检查它是否也是 de Bruijn 序列。
在可能生成的数百个字符串中，我只得到了一小部分（5-20 个，具体取决于 SIZE），结果证明是 de Bruijn 序列。我也不确定我是否应该做其他事情来解决这个问题。
我不确定的最后一件事是我如何区分 n。在我的例子中，以 8 位为例，因为有两条边，这意味着每个 8 位顶点都会产生一个 16 位结果。至少这就是它看起来正在做的事情。所以想知道如何更正它以生成 所有可能的 de Bruijn 序列 ，对于任何 SIZE?
Another code revision 结果似乎略有好转。
This talk/presentation 似乎说您可以通过某种方式从图中生成所有 de Bruijn 序列，但我已经看到了几种不同的构造边的方法，所以不确定“正确”的方法是，或者如果我有点正确的话。
我想通了，必须遍历哈密顿循环
// 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
}
流中的示例输出：
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
生成 n = 5 的所有 65536 个 de Bruijn 序列需要 1.5 分钟。对于 n > 5 它崩溃了，使用了太多的内存来生成所有的汉密尔顿循环。
我有 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，有欧拉循环。
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
}
首先，有一个SIZE属性。这表明整个程序有多少位。本例中为8。所以它生成8位（顶点）的所有排列，然后左右旋转，在每个顶点上生成两条向外的边。这将创建一个基本图形。然后它在这个图上做 DFS 来生成我猜的行走，然后输出一个从每个顶点开始的字符串。有一个函数 isDeBruijnSequence 可以检查它是否也是 de Bruijn 序列。
在可能生成的数百个字符串中，我只得到了一小部分（5-20 个，具体取决于 SIZE），结果证明是 de Bruijn 序列。我也不确定我是否应该做其他事情来解决这个问题。
我不确定的最后一件事是我如何区分 n。在我的例子中，以 8 位为例，因为有两条边，这意味着每个 8 位顶点都会产生一个 16 位结果。至少这就是它看起来正在做的事情。所以想知道如何更正它以生成 所有可能的 de Bruijn 序列 ，对于任何 SIZE?
Another code revision 结果似乎略有好转。
This talk/presentation 似乎说您可以通过某种方式从图中生成所有 de Bruijn 序列，但我已经看到了几种不同的构造边的方法，所以不确定“正确”的方法是，或者如果我有点正确的话。
我想通了，必须遍历哈密顿循环
// 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
}
流中的示例输出：
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
生成 n = 5 的所有 65536 个 de Bruijn 序列需要 1.5 分钟。对于 n > 5 它崩溃了，使用了太多的内存来生成所有的汉密尔顿循环。