Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def de_bruijn(k, n):
- """
- de Bruijn sequence for alphabet k
- and subsequences of length n.
- """
- try:
- # let's see if k can be cast to an integer;
- # if so, make our alphabet a list
- _ = int(k)
- alphabet = list(map(str, range(k)))
- except (ValueError, TypeError):
- alphabet = k
- k = len(k)
- a = [0] * k * n
- sequence = []
- def db(t, p):
- if t > n:
- if n % p == 0:
- sequence.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 "".join(alphabet[i] for i in sequence)
- print(de_bruijn(2, 3))
- print(de_bruijn("abcd", 2))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement