Instantly share code, notes, and snippets.

vincentdavis/gist:8588879

Last active January 4, 2016 07:29
Show Gist options
• 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
to join this conversation on GitHub. Already have an account? Sign in to comment