0
$\begingroup$

Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that

$A'_{1} = \{a_{1}, ...,a_{x}\}$

$A'_{2} = \{a_{x+1},...,a_{y}\}$

$...$

$A'_{k} = \{a_{z+1},...,a_{n}\}$

where each subarray $A'_{1},A'_{2}, ...,A'_{k}$ has sum of its elements closest to $\sigma; \sigma = \frac{\sum_{i = 1}^{n} {a_{i}}}{k}$

Example: $A = \{{5,6,1,3,4,10\}}, k = 3$

$\sigma = \frac{29}{3} = 9.\overline{66} \approx 10$

Best solution to split array is:

$A'_{1} = \{5,6\}$

$A'_{2} = \{1,3,4\}$

$A'_{3} = \{10\}$

with sums $11, 8, 10$

One way to measure "badness" of each solution, is to define function $h(A_{1},...,A_{k}) = \sum_{i = 1}^{k} {(s_{i} - \sigma)^2}$, where $s_{i}$ is sum of elements of subarray $A_{i}$

Can you point me towards the solution? I've been trying for a few days now, and I'm no closer to an algorithm than I was few days ago.

$\endgroup$
  • 1
    $\begingroup$ Where did you see this question? AI course? Algorithms course? What was the topic? $\endgroup$ – Gari BN Dec 21 '13 at 23:33
  • $\begingroup$ @DavidRicherby I think that unlike the classical Partition (NPC) problem, the elements in each subarray should be neighbors, so your solution is illegal. $\endgroup$ – Gari BN Dec 21 '13 at 23:35
  • $\begingroup$ I suppose from the given {5,6,1,3,4,10} array the most evenly distributed three sub arrays would be like {5,4}, {6,3,1} and {10} with sums 9, 10 and 10. $\endgroup$ – Redu Oct 7 '16 at 14:32
3
$\begingroup$

Use dynamic programming. This is a straightforward application of dynamic programming. This is a very nice exercise, so I'll let you do the exercise yourself and won't spoil it for you -- but since you only wanted a hint, my hint is "use dynamic programming" (that's a huge, enormous hint that should be enough for you to work out the rest of the details).

In particular, you should be able to solve this in $O(kn^2)$ time.

$\endgroup$
  • 1
    $\begingroup$ It sounds like a HW question. I believe that you gave him some new information only in complexity that you mentioned, as the headline of the exercise probably was something like "dynamic programming". =) I thought that such an exercise might be either for dynamic programming (in algorithms course) or for AI, to use algorithms like Hill-Climbing, IDA* or Iterative deepening by different heuristics. $\endgroup$ – Gari BN Dec 22 '13 at 7:29
  • $\begingroup$ In case of $k=2$ this problem is the "subset sum problem", or am i wrong? The subset sum problem is np-complete and therefore you would (probably) not be able to find a solution which works in $O(n^2)$ $\endgroup$ – user5187212 Oct 17 '18 at 16:47
  • 1
    $\begingroup$ @user5187212, nope, it's not subset sum. The arrays $A'_1,A'_2$ have to be contiguous, not arbitrary subsets. $\endgroup$ – D.W. Oct 17 '18 at 18:12
  • $\begingroup$ You are absolutely right. I missed that detail! Case $k=2$ is now trivial and can even be solved in linear time. $\endgroup$ – user5187212 Oct 17 '18 at 21:21
0
$\begingroup$

I faced a similar question in an algorithm exam. Where it was asked to minimize the individual $max(s_{i})$ over all such k- partitioning of n integers.

From your approach I made an algorithm that I goes as follows .

  1. total = total of all n-integers.
  2. p= no of parts , I initialise it to n at first and k'=k
  3. while p>k

    3a. let $s_{i}$_bound=$\lceil\frac{total}{k'+1}\rceil$

    3b. keep track of individual element sums, whenever the $t_{i}$ exceeds the constant $s_{i}$_bound , we update p by incrementing it

    3c. we decrease the value of k'

If we get partitions less than the required number then we can choose a required number of partitions whose sum is less than the bound and split it such that both have individual sums less than the bound. Invariance condition meted.

Runtime analysis : 3b. will run in O(n) and 3c. can decrease k' to a minimum of 1 as the least number of partitions can be 1.
So the worst case runtime will be of the order O(nk)


For my particular question I just need to have one more pass over the array and find the max sum which may be less than the bound I set.

$\endgroup$
  • $\begingroup$ I don't see clear your answer, why it's correct? $\endgroup$ – jonaprieto Oct 4 '14 at 23:30
  • $\begingroup$ I'm not saying its correct, actually! :-/ I made this algorithm and am running on random inputs to get partitions as required. I found it giving approximate correct answers. On several cases I found it giving wrong answers too, mainly for skewed distributions! for those I have altered to run through all values incrementing $s_{i}$_bound till it gives k required partitions! But doing so makes my runtime O(mn) where m= max sum of the partition among the partitions which is closest to $\sigma$. This looks like the runtime of floyd warshall where runtime is expressed in terms of the output. $\endgroup$ – Ramit Oct 6 '14 at 4:28
0
$\begingroup$

This is the game of inserting the biggest currently available number into the sub array with the smallest sum. So it is best done by sorting the main array first.

My approach would be like this;

  1. create an initial sub-arrays array in length given sub arrays count. sub arrays should have a sum property too. ie [[sum:0],[sum:0]...[sum:0]]
  2. sort the main array descending.
  3. start with search for the sub-array with the smallest sum value (initially they are all 0 and you will get the first sub array) and insert the first item (biggest) from the beginning of the main array and increment the sub arrays sum property by the inserted item's value.
  4. repeat item 3 one by one for each main array items up until the end of main array is reached.
  5. return the initial array.
$\endgroup$
  • 1
    $\begingroup$ Although the question uses set notation, the definition of the subarrays strongly suggests that they're supposed to be contiguous chunks of the original array. Sorting the original array breaks this property. I also misunderstood this point and posted a comment suggesting a "better" solution than the one in the question that used non-contiguous subarrays. (I deleted this comment just now. It was pointed out that it was wrong minutes after I posted it, nearly two years ago but, for some reason I didn't delete it, then. Apologies if it mislead you.) $\endgroup$ – David Richerby Oct 8 '16 at 12:16
0
$\begingroup$

There has been a solution in StackOverflow. It uses Backtracking algorithm like 8-queen problem. But this solution is brute-forcing with additional improvement. When $n\ge 400$ and $k\ge 8$, it takes lots of time!

$\endgroup$
  • 1
    $\begingroup$ Maybe you can briefly describe that algorithm (or even quote that answer). It would be better if one can understand this algorithm without clicking into that link. $\endgroup$ – xskxzr Mar 6 at 16:19
  • $\begingroup$ That answer on Stack Overflow question is a poor algorithm (it runs in exponential time, when there are polynomial-time algorithms available). There are other answers that describe better algorithms. $\endgroup$ – D.W. Mar 6 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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