Partitions of Equal Measure Whatever the Measure May Be

Description of the problem

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\).

The algorithm

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.

Why does it work?

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.

Implementation

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-COMPARE

Here 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-PARTITION

And 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)

Measure?