我有這段代碼，我把它放在一起試圖生成所有可能的 de Bruijn 序列，但沒有得到“預期”的結果。它使用（我認為被稱為）de Bruijn 圖，帶有歐拉回圈。
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 序列。
SIZE從可能生成的數百個字串中，我只得到了一小部分（5-20?? 個，具體取決于），這些字串結果是 de Bruijn 序列。我也不確定我是否應該做其他事情來解決這個問題。
我不確定的最后一件事是我如何區分n. 在我的例子中，以 8 位為例，因為有兩條邊，這意味著每個 8 位頂點都會產生一個 16 位的結果。至少它看起來是這樣的。所以想知道如何糾正這個以生成所有可能的 de Bruijn 序列，對于任何一個SIZE？
另一個代碼修訂和結果似乎變得稍微好一些。
這個談話/演示似乎說你可以以某種方式從一個圖中生成所有的 de Bruijn 序列，但我已經看到了一些不同的方式來構建邊緣等等，所以不確定“正確”的方法是什么，或者如果我說得對。
uj5u.com熱心網友回復：
我想通了，它必須是一個被遍歷的漢密爾頓回圈。
// 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
生成所有 65536 de Bruijn 序列需要 1.5 分鐘n = 5。因為n > 5它崩潰了，使用了太多的記憶體來生成所有的哈密頓回圈。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464745.html
標籤：javascript 算法 组合学