1

How would I go about splitting a sequence of numbers into four equal (as equal as possible) summations?

Say I have a sequence of 26 integers like so:

16, 4, 17, 10, 15, 4, 4, 6, 7, 14, 9, 17, 27, 6, 1, 9, 0, 12, 20, 8, 0, 3, 4, 0, 3, 4

I want to have it split into four chunks where the sum of all the integers in the chunk add up to roughly a quarter of the total value of the sequence. The total value of this sequence is 220 so I would want chunks roughly equal to 55.

For a bit of background: the numbers are representative of the number of entries in a phonebook that start with a certain letter. I'm trying to split the phonebook up in the best possible way.

Edit: It is important that the numbers stay in the sequence they are in now.

mforrest
  • 11
  • I asked pretty same Q, but with 2 groups(not four) with comment tell me to read bout partition problem : http://math.stackexchange.com/questions/889163/given-a-set-of-nonnegative-numbers-put-pm-between-them-to-minimize-the-magni – d_e Jul 03 '15 at 09:58
  • I think the solution uses Dynamic Programming. What you want is to find a solution where the max number of pages in each partition is minimal relative to other solutions. define a "recursive" formula, memoize the solution to sub problems in a table, compute the larger sub problem using allreadycalculated values. – Gil-Mor Jul 03 '15 at 10:13
  • 1
    @d_e Thanks for your comment. The difference between my problem and the partition problem is that my numbers are in a sequence and I have to find the best solution with that same sequence. – mforrest Jul 03 '15 at 10:14
  • you right.. if I'm not mistaken you have ${(n+1) \choose 3}$ options to split. interesting question. – d_e Jul 03 '15 at 10:19
  • If it's really only 4 partitions, than @d_e is right there are ${(n+1) \choose 3}$ ways to split meaning the complexity of checking all solutions is $\Theta(n^3)$. the dynamic programming solution might be $\mathcal{O}(n^2)$. for k partitions the DP algorithm will be$\mathcal{O}(n^2*k)$. – Gil-Mor Jul 03 '15 at 10:32
  • Actually I was mistaken. the number of ways to split into 4 partitions is ${(n+3) \choose 3}$ if you allow empty partitions or ${(n-1) \choose 3}$ if you don't according to this. The complexities are the same. – Gil-Mor Jul 03 '15 at 11:49

1 Answers1

0

Well, since I was looking for a solution for this Dynamic Programming problem some time ago and didn't find a solution online I'll write the solution now.. This solves the problem for $n$ elements and $k$ partitions where for each element (letter) $i$, $1 \le i \le n$, the size of the element (number of pages for this letter) is $P_i$.

Let $C[i, j]$ be the optimal solution for $i$ partitions of a set with $j$ elements . The optimal solution is a solution where the maximum number of pages in a partition is minimal relative to other solutions. so $C[k, n]$ is the optimal solution to the problem. Define the recursive formula $$ C[i,j] = \left\{\begin{aligned} &0 && j=0 \\ &\infty && i=0 \land j \ne 0 \\ &\min_{1 \le r \le j} \{ \max \{{ C[i-1, r], \sum_{s=r}^j{P_s }}\}\} && otherwise \end{aligned} \right.$$

What happening is this: In the first case where $j=0$ there are no letters and no pages so the sum of pages in the last partition is 0. In the second case you have pages to split but no available partitions so the sum of pages is $\infty$ (this is a sort of auxiliary case). In the last case, you assume you have an optimal solution for $i-1$ partitions of the $j$ elements, now you need to choose the sequence of elements you put in the last partition. You look in previous results and give the last partition all the elements starting from $1 \le r \le j$ which results in the minimal size of the biggest partition.

Taking the minimal maximum makes the partition balanced. If you'd just take the minimum, The size of another partition will grow.

With this recursive formula you fill a table where the rows 0 to $k$ represent the partitions and the columns 0 to $n$ represent the elements (letters in you case). You fill the table row by row, column by column relying on the recursive formula and former calculations to fill each cell $[i, j]$, it's best if you also save the $1 \le r \le j$ in each cell. that's the first element in the $i$th partition in a sequence of $j$ elements. After you've filled the table, you read the solution by starting from the last cell $[k, n]$ and tracing back, following the $i$'s and moving one row wards until you reach the cell $[0, 0]$.

Complexity: fill $k+1$ rows and $n+1$ columns. for each cell $[i, j]$ you examine all the cells $[i-1,1] \text{ to } [i-1, j]$. That's $\mathcal{O}(n^2)$ for each row so the total is $\mathcal{O}(k*n^2)$. reading the solution is $\mathcal{O}(k)$. So $\mathcal{O}(k*n^2)$. I explained it the best I could.. I hope this helps you in some way.

Gil-Mor
  • 305
  • @mforrest If you accept my answer please upvote it and mark as answered. If not please say what's wrong. – Gil-Mor Jul 03 '15 at 14:08