Clever Geek Handbook

Grouping seqs of different sizes - Clojure

I have the following data:

(def letters [:a :b :c :d :e :f :g ])
(def group-sizes [2 3 2])

What would be an idiomatic way to group letters by size, so what I end up with is:

[[:a :b] [:c :d :e] [:f :g]]

Thank.

+3


source to share


3 answers 


(->> group-sizes
     (reductions + 0)
     (partition 2 1)
     (map (partial apply subvec letters)))

This algorithm requires input coll to letters

be a vector and have at least the required number of elements (apply + group-sizes)

. It returns a lazy seq (or vector if you are using mapv

) vectors that share the structure with the input vector.



Thanks to subvec they are created in O (1), time constant, so the total time complexity should be O (N), where N is (count group-sizes)

, compared to Diegos's algorithm, where N will be significantly higher (count letters)

.

+9


source


After I started writing my answer, I noticed that Leon Grapentin's solution is almost identical to mine.

Here's my version:

(let [end   (reductions + group-sizes)
      start (cons 0 end)]
  (map (partial subvec letters) start end))


The only difference from Leon Grapentin 's solution is that I use let

and cons

instead of partition

and apply

.

Note that both solutions consume group-sizes

lazily, thus creating a lazy sequence as output.

+4


source


Not necessarily the best way (for example, you can check that the sum of the group sizes is the same as the letter sizes to avoid NPEs), but this was my first thought:

(defn sp [[f & r] l]
  (when (seq l)
    (cons (take f l)
          (sp r (drop f l)))))

You can also do this with an accumulator and recur

if you have a long list and don't want to blow up the stack.

+2


source






More articles:


All Articles