De Bruijn sequence

gistfile1.txt

def debruijn(k, n):
    """
    De Bruijn sequence for alphabet size k (0,1,2...k-1)
    and subsequences of length n.
    From wikipedia Sep 22 2013
    """
    a = [0] * k * n
    sequence = []
    def db(t, p,):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(int(a[t - p]) + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return ''.join(map(str, sequence))


_mapping = bytearray(b"?")*256
_mapping[:10] = b"0123456789"

def debruijn_bytes(k, n):
    """
    By Peter Otten on python-list
    """
    a = k * n * bytearray([0])
    sequence = bytearray()
    extend = sequence.extend
    def db(t, p):
        if t > n:
            if n % p == 0:
                extend(a[1: p+1])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence.translate(_mapping).decode("ascii")

if __name__ == "__main__":
    d1 = debruijn(4, 8)
    d2 = debruijn_bytes(4, 8)

    print(d1[:50])
    print(d2[:50])
    assert d1 == d2

$ python debruijn_compat.py
00000000100000002000000030000001100000012000000130
00000000100000002000000030000001100000012000000130
$ python3 debruijn_compat.py
00000000100000002000000030000001100000012000000130
00000000100000002000000030000001100000012000000130
$ python -m timeit -s 'from debruijn_compat import debruijn as d' 'd(4, 8)'
10 loops, best of 3: 53.5 msec per loop
    
$ python -m timeit -s 'from debruijn_compat import debruijn_bytes as d' 'd(4, 8)'
10 loops, best of 3: 22.2 msec per loop
    
$ python3 -m timeit -s 'from debruijn_compat import debruijn as d' 'd(4, 8)'
10 loops, best of 3: 68 msec per loop
    
$ python3 -m timeit -s 'from debruijn_compat import debruijn_bytes as d' 'd(4, 8)'
10 loops, best of 3: 21.7 msec per loop