generate De Bruijn sequence memory and string vs lists

[Peter Otten]

Vincent Davis wrote:

> On Thu, Jan 23, 2014 at 2:36 PM, Mark Lawrence
> <breamoreboy at yahoo.co.uk>wrote:
> 
>> FTR string.maketrans is gone from Python 3.2+.  Quoting from
>> http://docs.python.org/dev/whatsnew/3.2.html#porting-to-python-3-2 "The
>> previously deprecated string.maketrans() function has been removed in
>> favor of the static methods bytes.maketrans() and bytearray.maketrans().
>> This change solves the confusion around which types were supported by the
>> string module. Now, str, bytes, and bytearray each have their own
>> maketrans and translate methods with intermediate translation tables of
>> the appropriate type."
>>
> 
> ​Thanks for pointing this out Mark, ​I will soon be running this on 3.3+

Well, my first post in this thread head this suspicious comment:

> # Python 2
> def debruijn(k, n):
 
In hindsight I have no idea what I was trying to say ;)

Anyway, as a special service to Mark and Vincent here's an updated version 
that might work on both Python 2 and 3 (there's no test but the ad-hoc demo 
in the if __name__ == "__main__" block):

[debruijn is Vincents original code, debruijn_bytes my modified version]

$ cat debruijn_compat.py
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):
    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