Idiomatic string rotation in Clojure

Question

How to idiomatically rotate a string in Clojure for the Burrows-Wheeler transform?

I came up with this, which uses (cycle "string"), but feels a bit imperative:

(let [s (str "^" "banana" "|")
      l (count s)
      c (cycle s)
      m (map #(take l (drop % c)) (range l))]
  (apply map str m))
=> ("^banana|" "banana|^" "anana|^b" "nana|^ba" "ana|^ban" "na|^bana" "a|^banan" "|^banana")

I'm not sure if this qualifies as code golf. Is there a cleaner way to do this?

Answer 1

I would do:

(defn bwrot [s]
  (let [s (str "^" s "|")]
    (for [i (range (count s))]
      (str (subs s i) (subs s 0 i)))))

or:

(defn bwrot [s]
  (let [n (+ 2 (count s))
        s (str "^" s "|^" s "|")]
    (for [i (range n)]
      (subs s i (+ i n)))))

The second one should allocate less (one string instead of three per iteration).

Answer 2

If I was unconcerned about efficiency or number of characters I'd write something like:

(defn rotate-string
 [s]
 (apply str (concat (drop 1 s) (take 1 s))))

(defn string-rotations
  [s] 
  (->> s
       (iterate rotate-string)
       (take (count s))))

(rotate-string "^banana|") ; "banana|^"
(string-rotations "^banana|") ; ("^banana|" "banana|^" "anana|^b" "nana|^ba" "ana|^ban" "na|^bana" "a|^banan" "|^banana")

In particular, factoring out the single rotation into its own function.

Answer 3

A stepped call to partition works:

(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)))))))

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

Answer 4

There used to be a rotations function in clojure.contrib.seq that might be worth a look for inspiration. The source is reproduced below:

(defn rotations
  "Returns a lazy seq of all rotations of a seq"
  [x]
  (if (seq x)
    (map
     (fn [n _]
       (lazy-cat (drop n x) (take n x)))
     (iterate inc 0) x)
    (list nil)))

Then you could do something like:

(apply map str (rotations "^banana|"))
; => ("^banana|" "banana|^" "anana|^b" "nana|^ba" "ana|^ban" "na|^bana" "a|^banan" "|^banana")

Answer 5

Another way to accomplish rotation is to use a "double string" (i.e. concatenate the string to itself) and play around with substrings.

(defn rotations [strng]
  (let [indices (range (count strng))
        doublestr (str strng strng)]
    (map #(subs doublestr % (+ % (count strng))) indices)))

(rotations "^banana|")
;;(^banana| banana|^ anana|^b nana|^ba ana|^ban na|^bana a|^banan |^banana)

Rotations of "foo":

• Take the double string "foofoo"
• Length n of "foo" = 3
• The rotations are all the n substrings of "foofoo" that start with indices 0, 1, 2 and have the same length n