（Prolog）检查一个列表是否可以分为两个相等的子列表

Question

我正在使用Prolog尝试检查列表是否可以分为2个具有相等总和的sublists（subarrays）。

以下内容应该成功：[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]的示例中，由于子序列[1,2]和[3]具有相等的和，因此返回true。那是不允许的。相反，应将[1,3,2]分为子列表[1] / [3,2]和[1,3] / [2]。因此，它应该失败。

我不确定如何修改subL谓词以返回子列表而不是子序列。

这是我到目前为止的内容：

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, S),
    sum(R, S).

这里，我们检查左和右子列表的总和是否等于相同的总和S。但是，您需要稍微更改sum/2谓词，以使空列表的总和也为0。我将其保留为练习。
上面的方法不是很有效，因为它花费了[[O（n 
2）时间。您可以通过首先计算整个列表的总和，然后使谓词遍历列表，每次跟踪左侧元素的总和，以及右侧剩余的总和，来使其线性。我认为，通过首先以“幼稚”的方式解决它，您可能会发现将其实现为改进会更容易。