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

Groups > comp.lang.python > #64630 > unrolled thread

Re: generate De Bruijn sequence memory and string vs lists

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

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

#64630 — Re: generate De Bruijn sequence memory and string vs lists

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.

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web