Re: generate De Bruijn sequence memory and string vs lists topic

Vincent Davis wrote:

> For reference, Wikipedia entry for De Bruijn sequence
> http://en.wikipedia.org/wiki/De_Bruijn_sequence
>
> At the above link is a python algorithm for generating De Brujin
> sequences. It works fine but outputs a list of integers [0, 0, 0, 1, 0, 1,
> 1, 1] and I would prefer a string '00010111'. This can be accomplished by
> changing the last line from;
> return sequence
> to
> return ''.join([str(i) for i in sequence])
> See de_bruijn_1 Below.
>
> The other option would be to manipulate strings directly (kind of).
> I butchered the original algorithm to do this. See de_bruijn_2 below. But
> it is much slower and ungly.
>
> I am wanting to make a few large De Bruijin sequences. hopefully on the
> order of de_bruijn(4, 50) to de_bruijn(4, 100) (wishful thinking?). I
> don't know the limits (memory or time) for the current algorithms. I think
> I am will hit the memory mazsize limit at about 4^31. The system I will be
> using has 64GB RAM.
> The size of a De Brujin sequence is k^n
>
> My questions;
> 1, de_bruijn_2 is ugly, any suggestions to do it better?
> 2, de_bruijn_2 is significantly slower than de_bruijn_1. Speedups?
> 3, Any thought on which is more memory efficient during computation.
>
> #### 1 ####
> def de_bruijn_1(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 sequence #original
> return ''.join([str(i) for i in sequence])
>
> d1 = de_bruijn_1(4, 8)
>
> #### 2 ####
> def de_bruijn_2(k, n):
> global sequence
> a = '0' * k * n
> sequence = ''
> def db(t, p):
> global sequence
> global a
> if t > n:
> if n % p == 0:
> for j in range(1, p + 1):
> sequence = sequence + a[j]
> else:
> a = a[:t] + a[t - p] + a[t+1:]
> db(t + 1, p)
> for j in range(int(a[t - p]) + 1, k):
> a = a[:t] + str(j) + a[t+1:]
> db(t + 1, t)
> return sequence
> db(1, 1)
> return sequence
>
> d2 = de_bruijn_2(4, 8)

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