Split a list of integers into sublists of equal sum in linear time

user_5069802 0
Viewed 311

I found an algorithm to do this in the following way:

  1. Given list l, compute its sum s.
  2. Compute the following table:

(s,acc)

  1. (s,0)

  2. (s-x1,x1)

  3. (s-x1-x2,x1+x2)

    ...

n. (s-x1-...x_n-1,x1+x2+...+x_n-1)

while at each step you check whether the left element of the pair is equal to the second.

Then, this algorithm determines in linear time if your list can be splitted in two sublists so that each sublists sums the same quantity.

I've trying for a while to proof this formally. However, I'm beginning to think that this may only be valid for natural numbers and not for integers.

  1. Can you confirm this view?
  2. Can you give an algorithm to do this for integers and for linear complexity?

Edit (my solution up to now)

fun check_list :: "int list ⇒ int ⇒ int ⇒ bool" where
"check_list [] n acc = False" |
"check_list (x#xs) n acc = (if n = acc then True else (check_list xs (n-x) (acc+x)))"

fun linear_split :: "int list ⇒ bool" where
"linear_split [] = False" |
"linear_split [x] = False" |
"linear_split (x # xs) = check_list xs (sum_list xs) x"
algorithm
1 Answers

You're asked to divide the list (as it is) into two parts without reordering the items.

I've trying for a while to proof this formally.

Your algorithm is correct since you're basically covering every single possible split by basically moving a separator along the list:

 | O O O  split 1
 O | O O  split 2
 O O | O  split 3
 O O O |  split 4

Can you give an algorithm to do this for integers and for linear complexity?

Your algorithm works for integers as well. Again, because you're inspecting every possible solution and its complexity is linear since you're just iterating over list twice (first time for calculating sum)

user_5504780
Related