Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.79 KB | None | 0 0
  1. def de_bruijn(k, n):
  2.     """
  3.    de Bruijn sequence for alphabet k
  4.    and subsequences of length n.
  5.    """
  6.     try:
  7.         # let's see if k can be cast to an integer;
  8.         # if so, make our alphabet a list
  9.         _ = int(k)
  10.         alphabet = list(map(str, range(k)))
  11.  
  12.     except (ValueError, TypeError):
  13.         alphabet = k
  14.         k = len(k)
  15.  
  16.     a = [0] * k * n
  17.     sequence = []
  18.  
  19.     def db(t, p):
  20.         if t > n:
  21.             if n % p == 0:
  22.                 sequence.extend(a[1:p + 1])
  23.         else:
  24.             a[t] = a[t - p]
  25.             db(t + 1, p)
  26.             for j in range(a[t - p] + 1, k):
  27.                 a[t] = j
  28.                 db(t + 1, t)
  29.     db(1, 1)
  30.     return "".join(alphabet[i] for i in sequence)
  31.  
  32. print(de_bruijn(2, 3))
  33. print(de_bruijn("abcd", 2))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement