bwt.clj

; Burrows-Wheeler Transform (and inverse)
; http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

(def string-start \u0098)

(defn bwt [s]
  (map last
       (sort-by vec
                (take (inc (count s))
                      (iterate #(concat (rest %)
                                        (list (first %)))
                               (cons string-start s))))))

(defn inv-bwt [s]
  (rest
   (first
    (filter #(= (first %) string-start)
            (nth (iterate #(map cons s (sort-by vec %))
                          (map list s))
                 (dec (count s)))))))

(let [s "'Twas brillig, and the slithy toves
         Did gyre and gimble in the wabe:
         All mimsy were the borogoves,
         And the mome raths outgrabe."]
  (println (apply str (bwt s)))
  (println (apply str (inv-bwt (bwt s)))))

My attempt:

(defn bwt[s]
  (let [s' (str "^" s "|")
        c (cycle s')
        l (count s')]
    (map last (sort (apply map str (take l (partition l 1 c)))))))

(prn (apply str (bwt "banana")))
=> "|bnn^aaa"