1

I'm looking for a way to implement equal piles in a list that can take a list of N elements and split it in to M piles. Any remainders are added one at a time to each pile. I feel like there might be something already out there.

List:  [1 2 3 4 5 6 7 8 9]
M = 5

[[1] [2] [3] [4] [5]]; divided into equal piles with   remainder [6 7 8 9]

[[1 6] [2 7] [3 8] [4 9] [5]]; output

But the actual numbers in each pile I don't really care about. As long as the (count element) is +/- of all others.

I found partion-all, but it doesn't deal with the remainder the way I need to, and I couldn't get the program to take the last element of the generated list and stick it in to the previous piles.

4 Answers 4

6

group-by-based solution (no guarantees w.r.t. pile ordering)

If the items in the list might not be consecutive integers as obtained from range, you can apply the basic idea behind Diego's function to indices instead of the items themselves:

(defn piles [m xs]
  (->> xs
    (map-indexed (fn [i x] [(mod i m) x]))
    (group-by first)
    vals
    (mapv #(mapv peek %))))

Note that group-by will return a hash map for sufficiently large values of m, so this function cannot guarantee any particular ordering of the piles (in particular, shorter piles may arrive ahead of taller piles).

Example from the REPL:

(piles 5 [1 2 3 4 5 6 7 8 9])
;= [[1 6] [2 7] [3 8] [4 9] [5]]
(piles 5 [:a :b :c :d :e :f :g :h :i])
;= [[:a :f] [:b :g] [:c :h] [:d :i] [:e]]

partition-all-based solution alternating between piles

Alternatively, you can use partition-all and a custom version of map that only stops when all its inputs are empty:

(defn piles2 [m xs]
  (letfn [(mapv-all [f & colls]
            (loop [colls (map seq colls) ret []]
              (if (every? nil? colls)
                ret
                (recur (map next colls)
                       (conj ret
                         (mapv first (take-while some? colls)))))))]
    (->> xs
      (partition-all m)
      (apply mapv-all vector))))

This function always returns the piles in the "natural" order.

Example:

(piles2 5 [:a :b :c :d :e :f :g :h :i])
;= [[:a :f] [:b :g] [:c :h] [:d :i] [:e]]

partition-all-based solution preserving original item order

In response to the comment, here's a way to keep the original order of elements:

(defn piles3 [m xs]
  (let [cnt (count xs)
        l   (quot cnt m)
        r   (rem cnt m)
        k   (* (inc l) r)]
    (concat
      (partition-all (inc l) (take k xs))
      (partition-all l (drop k xs)))))

NB. this returns a seq of seqs; you could use (mapv vec …) to transform it into a vector of vectors.

Example:

(piles3 5 (range 32))
;= ((0 1 2 3 4 5 6) (7 8 9 10 11 12 13) (14 15 16 17 18 19) (20 21 22 23 24 25) (26 27 28 29 30 31))
(map count *1)
;= (7 7 6 6 6)
2
  • thanks! this is totally what I asked, and you anticipated me using list of lists for this! I was wondering how I can modify this to make it so that I get (piles 2 [1 2 3 4 5 6 7]) ; [[1 2 3 4] [5 6 7]], the ordering changed. I thought it would be easy for me to see how to change it! Oct 20, 2014 at 8:27
  • @user1639926 Just edited the answer to include a solution that works like that. Oct 20, 2014 at 17:05
2

You could do:

(defn piles [xs m]
  (vals (group-by #(mod % m) xs)))

And then

(piles [1 2 3 4 5 6 7 8 9] 5)

=> ([1 6] [2 7] [3 8] [4 9] [5])

0

A succinct - albeit slow - lazy solution:

(defn piles [n coll]
  (let [heads (take n (iterate rest coll))]
    (map (partial take-nth n) heads)))

For example

(piles 5 (range 1 10))
;((1 6) (2 7) (3 8) (4 9) (5))
0

A fast eager version:

(defn piles [n coll]
  (loop [ans (vec (repeat n []))
         i 0
         coll coll]
    (if-let [[x & xs] (seq coll)]
      (recur
        (update-in ans [i] conj x)
        (mod (inc i) n)
        xs)
      ans)))

... which returns a vector of vectors:

(piles 5 (range 1 10))
;[[1 6] [2 7] [3 8] [4 9] [5]]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.