Skip to content

Instantly share code, notes, and snippets.

@nbulischeck
Created November 1, 2018 23:35
Show Gist options
  • Save nbulischeck/a5ffa1b544b1baed3168cd576b572a25 to your computer and use it in GitHub Desktop.
Save nbulischeck/a5ffa1b544b1baed3168cd576b572a25 to your computer and use it in GitHub Desktop.
GDB Python Plugin to Generate De Bruijn Sequences
#!/usr/bin/env python
from itertools import islice
from string import ascii_lowercase
def de_bruijn(k, n):
try:
_ = int(k)
alphabet = list(map(str, range(k)))
except (ValueError, TypeError):
alphabet = k
k = len(k)
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return ''.join(alphabet[i] for i in sequence)
class Cyclic(gdb.Command):
"""Print cyclic sequences."""
def __init__ (self):
super (Cyclic, self).__init__ ("cyclic", gdb.COMMAND_USER)
def invoke(self, arg, from_tty):
try:
print(''.join(islice(de_bruijn(ascii_lowercase, 4), int(arg)+1)))
except ValueError:
print(arg, "must be an integer, but is not!")
class FindCyclic(gdb.Command):
"""Find cyclic sequences."""
def __init__ (self):
super (FindCyclic, self).__init__ ("find-cyclic", gdb.COMMAND_USER)
def invoke(self, arg, from_tty):
print(de_bruijn(ascii_lowercase, 4).find(arg))
Cyclic()
FindCyclic()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment