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)
Vincent Davis
--
https://mail.python.org/mailman/listinfo/python-list
