Skip to content

Instantly share code, notes, and snippets.

@rgov
Last active Jun 7, 2021
Embed
What would you like to do?
de Bruijn sequence generator
def deBruijn(n, k):
'''
An implementation of the FKM algorithm for generating the de Bruijn
sequence containing all k-ary strings of length n, as described in
"Combinatorial Generation" by Frank Ruskey.
'''
a = [ 0 ] * (n + 1)
def gen(t, p):
if t > n:
for v in a[1:p + 1]:
yield v
else:
a[t] = a[t - p]
for v in gen(t + 1, p):
yield v
for j in xrange(a[t - p] + 1, k):
a[t] = j
for v in gen(t + 1, t):
yield v
return gen(1, 1)
if __name__ == '__main__':
print ''.join([ chr(ord('A') + x) for x in deBruijn(3, 26) ])
@rgov

This comment has been minimized.

Copy link
Owner Author

@rgov rgov commented Apr 2, 2013

Modified this to use generators, but it could be cleaned up considerably with some itertools.

@Fiona1729

This comment has been minimized.

Copy link

@Fiona1729 Fiona1729 commented Jan 19, 2017

Is there any possibility of modification to allow it to generate f-fold k-ary De Bruijin sequences? As in a De Bruijin sequence that contains every string of length 3 at least five times?

@Connor-Irwin

This comment has been minimized.

Copy link

@Connor-Irwin Connor-Irwin commented Sep 17, 2020

A modified version I made:

def deBruijn(n, k):
   '''
   An implementation of the FKM algorithm for generating the de Bruijn
   sequence containing all k-ary strings of length n, as described in
   "Combinatorial Generation" by Frank Ruskey.
   '''
 
   a = [ 0 ] * (n + 1)
   
   def gen(t, p):
      if t > n:
         for v in a[1:p + 1]:
           yield v
      else:
         a[t] = a[t - p]
         
         for v in gen(t + 1, p):
           yield v
         
         for j in range(a[t - p] + 1, k):
            a[t] = j
            for v in gen(t + 1, t):
              yield v
   
   return gen(1, 1)
 
 
if __name__ == '__main__':
   #size of number combinations
   n=4
   
   #which base of numbers to use
   k=2


#be careful editing the stuff in this box
####################################################################
   sequence = ''                                                   #
   alpha_list = [chr(ord('A') + (x - 10)) for x in deBruijn(n, k)] #
   num_list = [str(x) for x in deBruijn(n, k)]                     #
                                                                   #
   for i in range(len(num_list)):                                  #
      if int(num_list[i]) > 9:                                     #
         sequence += alpha_list[i]                                 #
      else:                                                        #
         sequence += num_list[i]                                   #
####################################################################

   #comment and uncomment any section of code below
   #single line output
   print(sequence + '\n\nHuman readable:\n')
   
   #human readable output
   for i in range(len(sequence) - (n - 1)):
      alt_view = ''
      for e in range(n):
         alt_view += sequence[e + i]
      print(alt_view)



   #alphabetical only output
   #print(''.join([chr(ord('A') + x) for x in deBruijn(n, k)]))
   
   #base10 numerical output
   #print(''.join([str(x) for x in deBruijn(n, k)]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment