clojure - Get all moving k-sized partitions of a string

Question

I'm trying to get all "moving" partitions sized k of a string. Basically, I want to move a window of sized k along the string and get that k-word.

Here's an example,

k: 3

Input: ABDEFGH

Output: ABD, EFG, BDE, FGH, DEF

My idea was to walk along the input, drop a head and partition and then drop a head again from the previously (now headless) sequence, but I'm not sure exactly how to do this...Also, maybe there's a better way of doing this? Below is the idea I had in mind.

(#(partition k input) (collection of s where head was consecutively dropped))

Answer 1

Strings in Clojure can be treated as seqs of characters, so you can partition them directly. To get a sequence of overlapping partitions, use the version that accepts a size and a step:

user> (partition 3 1 "abcdef")
((\a \b \c) (\b \c \d) (\c \d \e) (\d \e \f))

To put a character sequence back into a string, just apply str to it:

user> (apply str '(\a \b \c))
"abc"

To put it all together:

user> (map (partial apply str) (partition 3 1 "abcdef"))
("abc" "bcd" "cde" "def")

Answer 2

Here are implementations of partition and partition-all for strings, returning a lazy-seq of strings, doing the splitting using subs. If you need high performance doing string transformations, these will be significantly faster (by average 8 times as fast, see criterium benchmarks below) than creating char-seqs.

(defn partition-string
  "Like partition, but splits string using subs and returns a
   lazy-seq of strings."
  ([n s]
     (partition-string n n s))
  ([n p s]
     (lazy-seq
      (if-not (< (count s) n)
        (cons
         (subs s 0 n)
         (->> (subs s p)
              (partition-string n p)))))))

(defn partition-string-all
  "Like partition-all, but splits string using subs and returns a
   lazy-seq of strings."
  ([n s]
     (partition-string-all n n s))
  ([n p s]
     (let [less (if (< (count s) n)
                  (count s))]
       (lazy-seq
        (cons
         (subs s 0 (or less n))
         (if-not less
           (->> (subs s p)
                (partition-string-all n p))))))))

;; Alex answer:
;; (let [test-str "abcdefghijklmnopqrstuwxyz"]
;;   (criterium.core/bench
;;    (doall
;;     (map (partial apply str) (partition 3 1 test-str)))))
;; WARNING: Final GC required 1.010207840526515 % of runtime
;; Evaluation count : 773220 in 60 samples of 12887 calls.
;; Execution time mean : 79.900801 µs
;; Execution time std-deviation : 2.008823 µs
;; Execution time lower quantile : 77.725304 µs ( 2.5%)
;; Execution time upper quantile : 83.888349 µs (97.5%)
;; Overhead used : 17.786101 ns

;; Found 3 outliers in 60 samples (5.0000 %)
;; low-severe    3 (5.0000 %)
;; Variance from outliers : 12.5585 % Variance is moderately inflated by outliers

;; KobbyPemson answer:
;; (let [test-str "abcdefghijklmnopqrstuwxyz"]
;;   (criterium.core/bench
;;    (doall
;;     (moving-partition test-str 3))))
;; WARNING: Final GC required 1.674347646128195 % of runtime
;; Evaluation count : 386820 in 60 samples of 6447 calls.
;; Execution time mean : 161.928479 µs
;; Execution time std-deviation : 8.362590 µs
;; Execution time lower quantile : 154.707888 µs ( 2.5%)
;; Execution time upper quantile : 184.095816 µs (97.5%)
;; Overhead used : 17.786101 ns

;; Found 3 outliers in 60 samples (5.0000 %)
;; low-severe       2 (3.3333 %)
;; low-mild         1 (1.6667 %)
;; Variance from outliers : 36.8985 % Variance is moderately inflated by outliers

;; This answer
;; (let [test-str "abcdefghijklmnopqrstuwxyz"]
;;   (criterium.core/bench
;;    (doall
;;     (partition-string 3 1 test-str))))
;; WARNING: Final GC required 1.317098148979236 % of runtime
;; Evaluation count : 5706000 in 60 samples of 95100 calls.
;; Execution time mean : 10.480174 µs
;; Execution time std-deviation : 240.957206 ns
;; Execution time lower quantile : 10.234580 µs ( 2.5%)
;; Execution time upper quantile : 11.075740 µs (97.5%)
;; Overhead used : 17.786101 ns

;; Found 3 outliers in 60 samples (5.0000 %)
;; low-severe    3 (5.0000 %)
;; Variance from outliers : 10.9961 % Variance is moderately inflated by outliers

Answer 3

(defn moving-partition 
    [input k] 
    (map #(.substring input % (+ k %)) 
        (range (- (count input) (dec k)))))