Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed2a.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 22:15:26 +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> <lbrst6$vel$1@ger.gmane.org> <lbrugd$k3a$1@ger.gmane.org> <CALyJZZU2J3n67LwF1a2-6eeMZ=J18zbj8h+QV-w7Ujz=kHkgOw@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.5909.1390511696.18130.python-list@python.org>
Lines: 99
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:64633

Vincent Davis wrote:

> On Thu, Jan 23, 2014 at 2:36 PM, Mark Lawrence
> <breamoreboy@yahoo.co.uk>wrote:
> 
>> FTR string.maketrans is gone from Python 3.2+.  Quoting from
>> http://docs.python.org/dev/whatsnew/3.2.html#porting-to-python-3-2 "The
>> previously deprecated string.maketrans() function has been removed in
>> favor of the static methods bytes.maketrans() and bytearray.maketrans().
>> This change solves the confusion around which types were supported by the
>> string module. Now, str, bytes, and bytearray each have their own
>> maketrans and translate methods with intermediate translation tables of
>> the appropriate type."
>>
> 
> ​Thanks for pointing this out Mark, ​I will soon be running this on 3.3+

Well, my first post in this thread head this suspicious comment:

> # Python 2
> def debruijn(k, n):
 
In hindsight I have no idea what I was trying to say ;)

Anyway, as a special service to Mark and Vincent here's an updated version 
that might work on both Python 2 and 3 (there's no test but the ad-hoc demo 
in the if __name__ == "__main__" block):

[debruijn is Vincents original code, debruijn_bytes my modified version]

$ cat debruijn_compat.py
def debruijn(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 ''.join(map(str, sequence))

_mapping = bytearray(b"?")*256
_mapping[:10] = b"0123456789"

def debruijn_bytes(k, n):
    a = k * n * bytearray([0])
    sequence = bytearray()
    extend = sequence.extend
    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 range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence.translate(_mapping).decode("ascii")

if __name__ == "__main__":
    d1 = debruijn(4, 8)
    d2 = debruijn_bytes(4, 8)

    print(d1[:50])
    print(d2[:50])
    assert d1 == d2

$ python debruijn_compat.py 
00000000100000002000000030000001100000012000000130
00000000100000002000000030000001100000012000000130
$ python3 debruijn_compat.py 
00000000100000002000000030000001100000012000000130
00000000100000002000000030000001100000012000000130
$ python -m timeit -s 'from debruijn_compat import debruijn as d' 'd(4, 8)'
10 loops, best of 3: 53.5 msec per loop
$ python -m timeit -s 'from debruijn_compat import debruijn_bytes as d' 
'd(4, 8)'
10 loops, best of 3: 22.2 msec per loop
$ python3 -m timeit -s 'from debruijn_compat import debruijn as d' 'd(4, 8)'
10 loops, best of 3: 68 msec per loop
$ python3 -m timeit -s 'from debruijn_compat import debruijn_bytes as d' 
'd(4, 8)'
10 loops, best of 3: 21.7 msec per loop