(Prolog) 检查一个列表是否可以分成 2 个总和相等的子列表

Question

我正在使用 Prolog 来尝试检查是否可以将列表拆分为 2 个 子列表（子数组），它们的总和相等。

以下应该成功：[1,2,3,6], [2,1,1], [0], [1,1,2]
以下应该失败：[1,4,8]、[1,3,2]、[2,2,1,1]

我相信我的程序正在创建 子序列 而不是 子列表 。这会导致类似于 [1,3,2] 和 [2,2,1,1] 的查询在应该失败的时候成功。

在查询 [1,3,2] 的示例中，它 return 为真，因为子序列 [1,2] 和 [3] 的总和相等。那不应该被允许。相反，[1,3,2] 应该分成子列表 [1]/[3,2] 和 [1,3]/[2]。因此，它应该失败。

我不确定如何将 subL 谓词修改为 return 子列表而不是子序列。

这是我目前的情况：

split([]).
split([0]).
split([H|T]) :- 
    subL([H|T], LEFT, RIGHT), 
    sum(LEFT, SUM1), 
    sum(RIGHT, SUM2),
    SUM1=SUM2.

subL([],[],[]).
subL([H|T], [H|T2], X) :- 
    subL(T, T2, X).
subL([H|T], X, [H|T2]) :- 
    subL(T, X, T2).

sum([H|T], SUM1) :- 
    sum(T, SUM2), 
    SUM1 is SUM2 + H.
sum([H], SUM1) :- 
    H = SUM1.

如有任何帮助，我们将不胜感激。谢谢

Answer 1

您可以使用 append 将列表拆分为不同的列表。确实：

?- append(L, R, [1,2,3,6]).
L = [],
R = [1, 2, 3, 6] ;
L = [1],
R = [2, 3, 6] ;
L = [1, 2],
R = [3, 6] ;
L = [1, 2, 3],
R = [6] ;
L = [1, 2, 3, 6],
R = [] ;
false.

所以你可以写一个谓词：

split(X) :-
    append(L, R, X),
    sum(L, <b>S</b>),
    sum(R, <b>S</b>).

这里我们检查左右子列表的总和是否相同S。但是，您略微需要更改 sum/2 谓词，使空列表的总和也为 0。我把它留作练习。

以上不是很有效，因为它需要 O(n²) 时间。您可以通过首先计算整个列表的总和使其成为线性，然后创建一个遍历列表的谓词，每次跟踪左侧元素的总和，以及右侧剩余的总和。我认为通过首先以 "naive" 方式解决它，您可能会发现更容易将其作为改进来实施。

(Prolog) 检查一个列表是否可以分成 2 个总和相等的子列表

(Prolog) Check if a list can be split into 2 sub-lists that have equal sums

prolog

subset

subset-sum