当前位置： 文江博客 话题详情

如何使用de bruijn图（在JavaScript中）生成所有de bruijn序列？

发布于 2025-01-23 07:03:31 字数 3676 浏览 0 评论 0 原文

我有 de bruijn图形，带有欧拉（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
}

首先，有一个 size 属性。这告诉整个程序中有多少位。在这种情况下，8。因此，它生成了8位（顶点）的所有排列，然后旋转左右旋转以在每个顶点上生成两个外边缘。这创建了一个基本图。然后，它可以在此图上进行DFS来生成步行，然后输出一个从每个顶点开始的字符串。有一个函数 isDebruijnSequence ，它也检查是否也是de bruijn序列。

我只从 size 中获得了一个小的（5-20​​），从生成的数百个字符串中，这些字符串被证明是de bruijn序列。我也不确定我是否应该做其他事情来正确解决这个问题。

我不确定的最后一件事是如何区分 n 。就我而言，以8位为例，由于有两个边，这意味着每个8位顶点将产生16位的结果。至少这就是它在做的事情。因此，对于任何 size ，我想知道如何对此进行纠正以生成所有可能的de bruijn序列？

此谈话/演示似乎您可以说您可以从一个de Bruijn序列中产生所有de bruijn序列以某种方式绘制图形，但是我看到了一些不同的方式来构造边缘等等，因此不确定“正确”的方法是什么，或者我有某种正确的方法。

原文

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.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（1）

绝不服输 2025-01-30 07:03:31

我弄清楚了，它必须是 hamiltonian循环。

// 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＆gt; 5 它崩溃了，使用过多的内存来生成所有哈密顿周期。

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.

回复 原文
~没有更多了~

关于作者

摇划花蜜的午后

暂无简介

文章
评论
25 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

tomoekana

文章 0 评论 0

无边思念无边月

文章 0 评论 0

眼角的笑意。

文章 0 评论 0

在风中等你

文章 0 评论 0

是你

文章 0 评论 0

syong71

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文