Path: csiph.com!usenet.pasdenom.info!dedibox.gegeweb.org!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed1a.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 21:10:06 +0100
Organization: None
References: <CALyJZZVU+j64Jn7fqqzLmwW+KcM=43UMKjo=HW7umnq8MSP2Uw@mail.gmail.com> <lbrjjq$96p$1@ger.gmane.org> <lbrlel$vpq$1@ger.gmane.org> <CALyJZZUn4XvTHSnsJhQwsM7CyXUJJis_BwwoZ8EYAQ209bvfig@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8Bit
User-Agent: KNode/4.7.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.5906.1390507780.18130.python-list@python.org>
Lines: 56
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:64630

Vincent Davis wrote:

> On Thu, Jan 23, 2014 at 12:02 PM, Peter Otten <__peter__@web.de> wrote:
>>
>> I just noted that the first Python loop can be eliminated:


Oops, I forgot to paste

import string
def chars(a, b):
    return "".join(map(chr, range(a, b)))
_mapping = string.maketrans(chars(0, 10), chars(48, 58))


>> 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)
> 
> 
> I am not really sure what _mapping should be. The code above does not run
> because
> NameError: global name '_mapping' is not defined
> I tried to get the bytearray
> ​ ​
> sequence to convert to ascii but don't know how to.

It does the same as adding 48 to every byte in the first variant:

>>> import string
>>> def chars(a, b):
...     return "".join(map(chr, range(a, b)))
... 
>>> _mapping = string.maketrans(chars(0, 10), chars(48, 58))
>>> b = bytearray(range(10))
>>> b
bytearray(b'\x00\x01\x02\x03\x04\x05\x06\x07\x08\t')
>>> b.translate(_mapping)
bytearray(b'0123456789')

The disadvantage of this approach is that it produces a new bytearray, i. e. 
it increases the peak amount of memory used by the function significantly.