Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #64624

Re: generate De Bruijn sequence memory and string vs lists

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: generate De Bruijn sequence memory and string vs lists Peter Otten <__peter__@web.de> - 2014-01-23 18:31 +0100

csiph-web