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

Question

I am using Prolog to try and check if a list can be split into 2 sublists(subarrays) that have equal sums.

The following should succeed: [1,2,3,6], [2,1,1], [0], [1,1,2]
The following should fail: [1,4,8], [1,3,2], [2,2,1,1]

I believe my program is creating subsequences instead of sublists. This is causing queries similar to [1,3,2] and [2,2,1,1] to succeed when they should fail.

In the example of the query [1,3,2] it is returning true because the subsequences [1,2] and [3] have equal sums. That should not be allowed. Instead, [1,3,2] should be split into sublists [1]/[3,2] and [1,3]/[2]. Hence, it should fail.

I am unsure how to modify the subL predicate to return sublists instead of subsequences.

Here is what I have so far:

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.

Any help with this would be greatly appreciated. Thank you

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2020-03-20T19:08:57

YOu can make use of append to split the list into different lists. Indeed:

?- 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.

so you can write a predicate:

split(X) :-
    append(L, R, X),
    sum(L, S),
    sum(R, S).

Here we thus check if both the left and the right sublist sum up to the same sum S. You however slighly need to change your sum/2 predicate such that the sum for an empty list is 0 as well. I leave that as an exercise.

The above is not very efficient, since it takes O(n²) time. You can make it linear by first calculating the sum of the entire list, and then make a predicate that iterates over the list, each time keeping track of the sum of the elements on the left side, and the remaining sum on the right side. I think that by first solving it the "naive" way, you likely will find it easier to implement that as an improvement.

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

1 Answers