de Bruijn sequence generator

debruijn.py

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) ])

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

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?

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)]))

I run it for (3, 2) and got:
10 :0001010111

Human readable:

000
001
010
101
010
101
011
111
There are 2 '101' but no '100'.

Nice catch @qiping. Perhaps there is an off by one error. The original source was this document (PDF), approximately page 219 -- but this gist is over 12 years old.