Last active
January 4, 2016 07:29
-
-
Save vincentdavis/8588879 to your computer and use it in GitHub Desktop.
De Bruijn sequence
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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): | |
""" | |
By Peter Otten on python-list | |
""" | |
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment