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)
    out = []

    def gen(t, p):
        if t > n:
            if n % p == 0:
                out.extend(a[1:p + 1])
        else:
            a[t] = a[t - p]
            gen(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                gen(t + 1, t)

    gen(1, 1)
    return out

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), chapter 7 -- but this gist is over 12 years old.

I resolved an issue with a missing condition. With @qiping's test case n=3, k=2, the correct output is 00010111. Note that 100 is missing because the sequence is cyclical. You can use seq + seq[:n-1] to wrap it around and explicitly include the 100 as in 00010111 00.

Verified against the test cases given in Ruskey (2003) and by explicitly checking all combinations are present.

I updated the code to run on Python 3. Turns out generators are slower than just accumulating the output a list.