Assume we have a finite list of real numbers \(a_1,\ldots,a_n\) that we want to split into \(k\) piles. But we would like to split them in such a way that the sum of the numbers in each pile is approximately the same.
I don’t know if there is a nice solution for the general case, but I have a solution if there is an \(m\) such that \(k = \lceil \frac{n}{2^m} \rceil\).
Assume I already have \(p\) piles each approximately equal size. Sort the piles according to the sum of the numbers in each pile. Now, pick the head and the tail and merge these piles. Continue until all piles are merged. Now, we have \(\lceil \frac{p}{2} \rceil\) piles. Continue until the desired number of piles is achieved.
The short answer: it doesn’t.
The long answer: It works depending on the distribution of the original list of numbers. If the distribution has fat points (i.e. accumulation points) then you’ll see the effect in the answer. If the orginal list comes from a uniformly distributed random variable the resulting piles would be roughly of equal size.
First, I will need a function that compares two piles of numbers according to the sum of the numbers within each pile.
(defun bag-compare (u v)
(apply #'<= (mapcar (lambda (w)
(reduce #'+ w))
(list u v))))
BAG-COMPAREHere is a recursive implementation of a solution in Common Lisp.
(defun equal-partition (bag k)
(labels
((aux (x m)
(if (<= m k)
(sort x #'bag-compare)
(let* ((a (sort x #'bag-compare))
(n (length a))
(res nil))
(dotimes (i (floor n 2) res)
(push (append (elt a i) (elt a (- n i 1))) res))
(aux res (floor m 2))))))
(aux (mapcar #'list bag) (length bag))))
EQUAL-PARTITIONAnd a test
(defvar res1 (equal-partition (loop repeat 80 collect (random 1.0)) 5))
RES1
(mapcar (lambda (x) (reduce #'+ x)) res1)
(8.534256501248814 8.538443573882267 8.54105577538768 8.541423618833738
8.542957284773246)
(defvar res2 (equal-partition (loop repeat 48 collect (random 10)) 3))
RES2
(mapcar (lambda (x) (reduce #'+ x)) res2)
(64 64 64)Now, notice that instead of the bag-compare function, I
could have used another function by changing the measure: instead of
adding the numbers, we could do other things such as a weighted sum, the
counting measure, a Dirac measure, or whatever…