python deBruijn sequence generator

gistfile1.txt

# translated from this : https://github.com/jgeisler0303/deBruijnDecode/blob/gh-pages/decodableDeBruijn.js

class DeBruijn:
    def __init__(self, c, n):
        self.c = c
        self.n = n
        self.a = [0] * (c * n)
        self.s = []
        for j in range(c * n):
            self.a[j] = 0
        self.generate(1, 1)
    
    def generate(self, t, p):
        if t > self.n:
            if self.n % p == 0:
                for j in range(p):
                    self.s.append(self.a[j+1])
        else:
            self.a[t] = self.a[t-p]
            self.generate(t+1, p)
            for j in range(self.a[t-p]+1, self.c):
                self.a[t] = j
                self.generate(t+1, t)

def mod(n, m):
    n = n % m
    if n < 0:
        n += m
    return n

def gcd(a, b):
    if a < 0:
        a = -a
    if b < 0:
        b = -b
    if b > a:
        temp = a
        a = b
        b = temp
    while True:
        a %= b
        if a == 0:
            return b
        b %= a
        if b == 0:
            return a

def sum(a):
    s = 0
    for i in range(len(a)):
        s += a[i]
    return s

def diff(a):
    s = [0] * (len(a) - 1)
    for i in range(1, len(a)):
        s[i-1] = a[i] - a[i-1]
    return s

def cumsum(a):
    for i in range(1, len(a)):
        a[i] = a[i-1] + a[i]
    return a

def wordIndex(w, c):
    idx = 0
    b = 1
    for i in range(len(w)):
        idx += b * w[i]
        b *= c
    return idx

def findWord(s, w):
    k = None
    n = len(w)
    s_ = s + s[:n]
    wi = 0
    k = 0
    while k < len(s) and wi != n :
        k += 1
        wi = 0
        while wi < n and s_[k+wi]==w[wi] :
            wi += 1
    if k >= len(s) :
        k = -1
    return k

def findOnes(s, n):
    w = [1] * n
    return findWord(s, w)


def decodableDeBruijn(c, n):

    def operator_D_inv(s, b, c):
        w = sum(s) % c
        if w != 0:
            s_ = s
            for i in range(c // gcd(c, w) - 1):
                s = s + s_
        s = cumsum(s[:-1])
        s.insert(0, 0)
        for i in range(len(s)):
            s[i] = (s[i] + b) % c
        return s

    def rho(p, e, s):
        s_ = s
        s = s[:p]
        e_ = []
        for i in range(e, e + c):
            e_.append(i % c)
        s = s + e_
        s = s + s_[p:]
        return s

    if n <= 2:
        db = DeBruijn(c, 2)
        t = db.s
        t_ = t + t[:2]
        for i in range(c ** 2):
            T[wordIndex(t_[i:i+2], c)] = i
    else:
        n_ = n - 1
        s = decodableDeBruijn(c, n_)
        k = findOnes(s, n_)
        s_ = s[:k] + s[k+1:]
        s_hat = operator_D_inv(s_, 0, c)
        p = (c - 1) * (c ** n_ - 1) + k
        e = s_hat[p]
        t = rho(p, e, s_hat)
        L[n-3] = t[:c ** n_ - 1]
    K[n-2] = findOnes(t, n)
    return t



def decodeDeBruijn(w, c):

    def operator_D(w, c):
        dw = [w[i+1] - w[i] for i in range(len(w)-1)]
        dw = [x % c for x in dw]
        return dw
    
    r = 2
    n = len(w)
    if n == r:
        return T[wordIndex(w, c)]
    
    v = operator_D(w, c)
    i = n - r - 1
    k = K[n - r - 1]
    p = (c - 1) * (c ** (n - 1) - 1) + k
    allOnes = all(x == 1 for x in v)
    
    if allOnes:
        e = L[n - r - 1][k] + (c - 1) ** 2
        j = p + (w[0] - e) % c
    else:
        f = decodeDeBruijn(v, c)
        if f > k:
            f = f - 1
        e = L[n - r - 1][f]
        j = f + (c ** (n - 1) - 1) * (e - w[0]) % c
        if j < 0 or j > p - 1:
            j = j + c
    
    return j




c = 4 # alphabet size
n = 8 # word length
T = [0] * (c ** 2)
L = [0] * (n - 2)
K = [0] * (n - 1)
s = decodableDeBruijn(c, n)
print(s)
print(len(s))