Skip to content

Instantly share code, notes, and snippets.

@cgrand cgrand/de-bruijn.clj
Created Sep 29, 2017

Embed
What would you like to do?
; 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.