2

如何在 Clojure 中为Burrows-Wheeler 变换惯用地旋转字符串？

我想出了这个，它使用(cycle "string")，但感觉有点必要：

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

我不确定这是否符合代码高尔夫的条件。有没有更清洁的方法来做到这一点？

4

5 回答 5

5

我会做：

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

或者：

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

第二个应该分配更少（一个字符串而不是每次迭代三个）。

于 2015-02-25T15:00:27.010 回答
3

曾经有一个rotations功能clojure.contrib.seq可能值得寻找灵感。来源转载如下：

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

然后你可以做类似的事情：

(apply map str (rotations "^banana|"))
; => ("^banana|" "banana|^" "anana|^b" "nana|^ba" "ana|^ban" "na|^bana" "a|^banan" "|^banana")
于 2015-02-25T18:15:20.943 回答
1

逐步调用partition作品：

(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"
于 2015-02-25T15:05:20.090 回答
1

如果我不关心效率或字符数，我会写如下内容：

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

特别是，将单个旋转分解为它自己的函数。

于 2015-02-25T15:01:44.303 回答
0

完成旋转的另一种方法是使用“双字符串”（即将字符串连接到自身）并使用子字符串。

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

“foo”的旋转：

  • 取双字符串“foofoo”
  • n“foo”的长度= 3
  • 旋转是n“foofoo”的所有以indices0、1、2 开头并且长度相同的子字符串n
于 2017-02-08T12:22:14.427 回答