Skip to content

Instantly share code, notes, and snippets.

@lenaschoenburg
Created July 7, 2013 15:00
Show Gist options
  • Save lenaschoenburg/5943729 to your computer and use it in GitHub Desktop.
Save lenaschoenburg/5943729 to your computer and use it in GitHub Desktop.
Burrows–Wheeler transformation.
(defn enhance [s]
(conj (into [\^] (vec s) )\|))
(defn rotate [c]
(vec (conj (drop-last c) (last c) )))
(defn pipe-and-save
"Given an item, it will recursivly apply fun n times. Gives back item plus each step in a coll"
([item n fun]
(pipe-and-save item n fun []))
([item n fun saved]
(if (= n 0)
saved
(let [applied (fun item)]
(recur applied (dec n) fun (conj saved applied))))))
(defn bwt [c]
(into [] (map last (sort (pipe-and-save (enhance c) 8 rotate)))))
(bwt "banana")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment