generate De Bruijn sequence memory and string vs lists

[Peter Otten]

Peter Otten wrote:

> You could change de_bruijn_1() to use `bytearray`s instead of `list`s:
> 
> # Python 2
> def debruijn(k, n):
>     a = k * n * bytearray([0])
>     sequence = bytearray()
>     append = sequence.append # factor out method lookup
>     def db(t, p,):
>         if t > n:
>             if n % p == 0:
>                 for j in xrange(1, p + 1):
>                     append(a[j]+48) # add 48 to convert to ascii
>         else:
>             a[t] = a[t - p]
>             db(t + 1, p)
>             for j in xrange(a[t - p] + 1, k):
>                 a[t] = j
>                 db(t + 1, t)
>     db(1, 1)
>     return sequence

I just noted that the first Python loop can be eliminated:

def debruijn(k, n):
    a = k * n * bytearray([0])
    sequence = bytearray()
    extend = sequence.extend # factor out method lookup
    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 xrange(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence.translate(_mapping)