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

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.