在线性时间内将整数列表拆分为相等总和的子列表 [英] Split a list of integers into sublists of equal sum in linear time
问题描述
我找到了一种算法，可以通过以下方式实现：
I found an algorithm to do this in the following way:
- 给出列表l，计算其总和s。
- 计算下表：
（s，acc）
- （s，0）
- （s-x1，x1）
-
（s-x1-x2，x1 + x2）
- (s,0)
- (s-x1,x1)
(s-x1-x2,x1+x2)
...
n。 （s-x1 -... x_n-1，x1 + x2 + ... + x_n-1）
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.
- 您可以确认此视图吗？
- 您可以提供一种算法来对整数和线性复杂度？
编辑（我的解决方案到目前为止）
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"
推荐答案
系统要求您将列表（按原样）分为两部分，而无需重新排序项目。
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?
您的算法也适用于整数。再一次，因为您正在检查每个可能的解决方案，并且它的复杂度是线性的，因为您只遍历了列表两次（第一次计算 sum ）
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)
这篇关于在线性时间内将整数列表拆分为相等总和的子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
