generate De Bruijn sequence memory and string vs lists

Vincent Davis vincent at vincentdavis.net
Fri Jan 24 08:20:49 EST 2014


On Fri, Jan 24, 2014 at 2:29 AM, Gregory Ewing
<greg.ewing at canterbury.ac.nz>wrote:

> If all you want is a mapping between a sequence of
> length n and compact representation of it, there's
> a much simpler way: just convert it to a base-k
> integer, where k is the size of the alphabet.
>
> The resulting integer won't be any larger than an
> index into the de Bruijn sequence would be, and
> you can easily recover the original sequence from
> its encoding without needing any kind of lookup
> table.
>

​True, ​the "all you want is a mapping" is not quite true. I actually plan
to plot frequency (the number of times an observed sub sequence overlaps a
value in the De Bruijn sequence) The way the sub sequences overlap is
important to me and I don't see a way go from base-k (or any other base) to
the index location in the De Bruijn sequence. i.e. a decoding algorithm.


Vincent Davis
720-301-3003
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20140124/379019d1/attachment.html>


More information about the Python-list mailing list