{{ message }}

Instantly share code, notes, and snippets.

# rgov/debruijn.py

Last active Jun 7, 2021
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 commented Apr 2, 2013

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

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