Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: generate De Bruijn sequence memory and string vs lists
Date: Thu, 23 Jan 2014 18:31:31 +0100
Organization: None
References: <CALyJZZVU+j64Jn7fqqzLmwW+KcM=43UMKjo=HW7umnq8MSP2Uw@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
User-Agent: KNode/4.7.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.5901.1390498260.18130.python-list@python.org>
Lines: 102
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:64624

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