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

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.