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

Groups > comp.lang.python > #64630

Re: generate De Bruijn sequence memory and string vs lists

Show key headers only | View raw

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.

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 21:10 +0100

csiph-web