de-bruijn.clj

; ported from https://en.wikipedia.org/wiki/De_Bruijn_sequence#Algorithm
(defn- de-bruijn "generate de-bruijn sequences of size n and with elements in 0..k (k excluded)." [k n]
  (let [a (into [] (repeat (* k n) 0))
        db (fn db [a t p]
             (if (> t n)
               (into a (when (zero? (mod n p)) (subvec a 1 (inc p))))
               (let [a (assoc a t (nth a (- t p)))
                     a (db a (inc t) p)]
                 (reduce 
                   (fn [a j]
                     (db (assoc a t j) (inc t) t))
                   a (range (inc (nth a (- t p))) k)))))
        a (db a 1 1)]
    (subvec a (* k n))))

=> (de-bruijn 4 2)
[0 0 1 0 2 0 3 1 1 2 1 3 2 2 3 3]