generate De Bruijn sequence memory and string vs lists
Peter Otten
__peter__ at web.de
Thu Jan 23 13:02:55 EST 2014
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)
More information about the Python-list
mailing list