Vincent Davis wrote:
> On Thu, Jan 23, 2014 at 2:36 PM, Mark Lawrence
> <(E-Mail Removed)>wrote:
>
>> FTR string.maketrans is gone from Python 3.2+. Quoting from
>> http://docs.python.org/dev/whatsnew/...-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
