Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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