(Пролог) Проверьте, можно ли разбить список на 2 подсписка с одинаковыми суммами

Question

Я использую Пролог, чтобы попытаться проверить, можно ли разбить список на 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] он возвращает true, поскольку подпоследовательности [1,2] и [3] имеют равные суммы. Это не должно быть позволено. Вместо этого [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, <b>S</b>),
    sum(R, <b>S</b>).

Здесь мы таким образом проверяем, совпадают ли левый и правый подсписки с одинаковой суммой S. Однако вам нужно немного изменить предикат sum/2, чтобы сумма для пустого списка была также 0. Я оставляю это как упражнение.

Вышеприведенное не очень эффективно, так как занимает O (n ² ) время. Вы можете сделать его линейным, сначала вычислив сумму всего списка, а затем сделайте предикат, который перебирает список, каждый раз отслеживая сумму элементов слева и оставшуюся сумму справа. Я думаю, что сначала решив это «наивным» способом, вам, вероятно, будет легче реализовать это как улучшение.