On Fri, Sep 23, 2011 at 7:51 AM, Michael Jaaka
<[email protected]> wrote:
> Hi!
>
> I have a sequence of natural numbers and I have to partition them into
> more or less equals N groups.
> Partitioning function is just a sum of numbers in a given group.
>
> My naive solution is to sort numbers descending then take each number
> and put into one of N groups in which sum of its elements with given
> number is the lowest. Here is the code: http://pastebin.com/Nw28FaRK
>
> So for input [ 1 2 34 54 12 23 5 2 3 1 2 12 11 12 32 67 ] and N = 5
> I get
> ([32 12 5 1 1] [34 12 2 2] [23 12 11 3 2] [54] [67])
>
> Do you know any better solution?
Seems like a good algorithm. Here's another implementation:
(defn partition-into [f n coll]
(map peek
(reduce
(fn [buckets x]
(let [b (first buckets), b2 (conj (b 2) x)]
(conj (disj buckets b) [(apply f b2) (b 1) b2])))
(apply sorted-set (for [i (range n)] [0 i []]))
(reverse (sort coll)))))
This only computes the sum once each time a partition is added to
(instead of multiple times during the sort), and because it's using a
sorted set only has to compare the sum to log(n) other buckets each
time instead of doing an n*log(n) sort-by.
--Chouser
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
