using greedy algorithm search in lists

Question

Given a list of positive integer Items whose elements are guaranteed to be in sorted ascending order, and a positive integer Goal, and Output is a list of three elements [A,B,C] taken from items that together add up to goal. The Output must occur inside the items list in that order (ascending order).

ex:

?- threeSum([3,8,9,10,12,14],27,Output).
Output=[8,9,10];
Output=[3,10,14].

someone helped me to reach this to this code but it gives me singleton variables:[Input,Items] ,it didnt work although iam not quite sure if this is a greedy algorithm search or not ?

 threeSum(Input,Goal,[A,B,C]):-
  permutation(Items, [A,B,C|Rest]),
  msort([A,B,C],[A,B,C]),
  msort(Rest,Rest),
  sum_list([A,B,C],Goal).

Answer 1

nums_goal_answer(Input, Goal, [A,B,C]) :-
    length(Input, InputLen),    
    reverse(Input, RInput),     % 'greedy' interpreted as 'prefer larger values first'.
                                % and larger values are at the end.

    between( 1, InputLen, N1),   
    between(N1, InputLen, N2),  % three nested for-loops equivalent.
    between(N2, InputLen, N3),


    \+ N1 = N2,                 % can't pick the same thing more than once.
    \+ N2 = N3,

    nth1(N1, RInput, A, _),
    nth1(N2, RInput, B, _),
    nth1(N3, RInput, C, _),

    sum_list([A,B,C], Goal).

someone helped me to reach this to this code but it gives me singleton variables:[Input,Items], it didnt work

The warning is because the code never looks at the numbers in the Input list. Without doing that, how could it ever work?

although iam not quite sure if this is a greedy algorithm

is it taking the biggest things first? I don't think permutation will do that.

Answer 2

A clpfd approach:

:- use_module(library(clpfd)).

threeSum(Input, Goal, [A,B,C]) :-
    Input = [First|Rest],
    foldl([N,M,T]>>(T = N\/M), Rest, First, Domain),

    [A,B,C] ins Domain,
    all_different([A,B,C]),
    chain([A,B,C], #>=),

    Goal #= A + B + C,

    labeling([max(A), max(B), max(C)], [A,B,C]).

Which has a bit of wrangling to turn the list of numbers into a domain, then says [A,B,C] must be in the list of numbers, must be different numbers, must be in descending order, must sum to the goal, and the clpfd solver should strive to maximise the values of A then B then C. (This probably won't work if the list can contain multiple of the same value like [5,5,5,3,2]).

e.g.

?- threeSum([3,8,9,10,12,14], 27, Output).
Output = [14, 10, 3] ;
Output = [10, 9, 8]

Answer 3

Using DCG:

:- use_module(library(dcg/basics)).

three_sum_as_dcg(Total, Lst, LstThree) :-
    phrase(three_sum_dcg(3, Total), Lst, LstThree).

% When finished, remove the remainder, rather than add to LstThree
three_sum_dcg(0, 0) --> remainder(_).

three_sum_dcg(NumsLeft, Total), [N] -->
    % Use this element
    [N],
    {   three_sum_informed_search(NumsLeft, Total, N),
        succ(NumsLeft0, NumsLeft),
        Total0 is Total - N
    },
    three_sum_dcg(NumsLeft0, Total0).

three_sum_dcg(NumsLeft, Total) -->
    % Skip this element
    [N],
    { three_sum_informed_search(NumsLeft, Total, N) },
    three_sum_dcg(NumsLeft, Total).
    
three_sum_informed_search(NumsLeft, Total, N) :-
    NumsLeft > 0,
    % "Informed" search calc due to list nums not decreasing
    Total >= (N * NumsLeft).

Result in swi-prolog (note the efficiency):

?- numlist(1, 1000000, L), time(findall(L3, three_sum_as_dcg(12, L, L3), L3s)).
% 546 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 4740036 Lips)
L3s = [[1,2,9],[1,3,8],[1,4,7],[1,5,6],[2,3,7],[2,4,6],[3,4,5]].

Answer 4

Restating the problem statement:

Given that I have

• A [source] list of positive integers, whose elements are guaranteed to be sorted in ascending order, and
• a positive integer indicating the target value.

I want to find

• an ordered subset of elements of the source list that sum to the target value

The simplest way is often the easiest (and the most general):

sum_of( _      , 0 , []     ) .  % nothing adds up to nothing.
sum_of( [X|Xs] , S , [X|Ys] ) :- % otherwise...
    S >  0 ,                     % - if the target sum S is positive,
    X =< S ,                     % - and the head of the list is less than or equal to the target sum
    S1 is S-X ,                  % - remove that amount from the target sum, and
    sum_of(Xs,S1,Ys) .           % - recurse down with the new target sum
sum_of( [_|Xs] , S , Ys     ) :- % then, on backtracking...
    S > 0 ,                      % - assuming that the target sum is positive,
    sum_of(Xs,S,Ys).             % - recurse down again, discarding the head of the list

This will find whatever combinations of however many list elements sum to the target value. It will find them from left to right, so

sum_of( [1,2,3,4,5,6,7,8,9], 10, L ).

will, on backtracking successively find

L = [ 1, 2, 3, 4 ]
L = [ 1, 2, 7    ]
L = [ 1, 3, 6    ]
L = [ 1, 4, 5    ]
L = [ 1, 9       ]
L = [ 2, 3, 5    ]
L = [ 2, 8       ]
L = [ 3, 7       ]
L = [ 4, 6       ]

If you want to change the order so it finds the largest values first, simply reverse the order of clauses 2 and 3 in sum_of/3:

sum_of( _      , 0 , []     ) .
sum_of( [_|Xs] , S , Ys     ) :-
    S > 0 ,
    sum_of(Xs,S,Ys) .
sum_of( [X|Xs] , S , [X|Ys] ) :-
    S >  0 ,
    X =< S ,
    S1 is S-X ,
    sum_of(Xs,S1,Ys) .

Now it will return the same set of solutions, just in the reverse order, starting with [4,6] and finishing with [1,2,3,4].

Once you have solved the general problem, it's a simple matter of restricting it to a specified number of elements, for instance:

sum_of_n_elements(Xs,N,S,Ys) :- length(Ys,N), sum_of(Xs,S,Ys).

And to get just the 3-element subsets that sum to the target value:

sum_of_3_elements(Xs,S,Ys) :- sum_of_n_elements(Xs,3,S,Ys) .

https://swish.swi-prolog.org/p/XKjdstla.pl