Prolog search for possible combination for subtracting 2 elements from a list

Question

This is an extended problem from this page. Prolog possible removal of elements in a list

For example, for a list X = [1,2,3], I can subtract like following:

subtract 1 from 1st / 2nd element, and X becomes [1-1, 2-1, 3] = [0, 1, 3] = [1, 3]

subtract 1 from 1st / 3rd element: X becomes [2, 2]

subtract 1 from 2nd / 3rd element: X becomes [1, 1, 2]

subtract 2 from 2nd / 3rd element: X becomes[1, 1]

So, it is always subtracting 2 elements, and with the same number, but always a real number. Have anyone got any ideas on this?

This looks better:

subt_comb(X, Y).
X = [1,2,3]
Y = [1,3]
Y = [2,2]
Y = [1,1,2]
Y = [1,1]

After having a look on the solutions of lurker and gusbro, I have created something like this.

remove2([HX|T], S2):-
    between(1, HX, Y),
    remove2__([HX|T], Y, S2).
remove2([HX|T], [HX|TY]):-
    remove2(T, TY).

% remove2__(S1, Y, S2), this procedure is to execute 0 after
% subtraction. Y is generated from remove2(S1, S2).
remove2__([Y|T], Y, TY):- remove2_(Y, T, Y, TY).
remove2__([HX|T], Y, [HY|TY]):-
    HX>Y,
    HY is HX - Y,
    remove2_(HX, T, Y, TY).


% remove2_(HX, L, Y, S2).
% HX is the first element from the origin list. L is the tail of the
% origin list. Y is the number to subtract. S2 is the result.
remove2_(_, [H|T], H, T).
remove2_(_, [H|T], Y, [HY|T]):-   %for list with descending order
    HY is H - Y, HY >0.
remove2_(HX, [H|T], Y, [H|TY]):-   %going for another element.
    remove2_(HX, T, Y, TY).


?- remove2([3,2,1],X).
X = [2, 1, 1] ;
X = [2, 2] ;
X = [1, 1] ;
X = [3, 1] ;
false.

?- remove2([1,2,3],X).
X = [1, 3] ;
X = [2, 2] ;
X = [1, 1, 2] ;
X = [1, 1] ;
false.

Answer 1

I would use 2 procedures.

The first one takes an item from the list, computes a number equal or lesser than it and then calls second procedure to subtract that number from another item in the remaining list.

You have to take care of border cases (if computed number is equal to item, then remove the item altogether), thus I use a different clause for those cases.

subt_comb([N|Tail], [NX|NTail]):-
  succ(N1, N),
  between(1, N1, NX),
  subt_comb1(Tail, NX, NTail).
subt_comb([N|Tail], NTail):-
  subt_comb1(Tail, N, NTail).
subt_comb([N|Tail], [N|NTail]):-
  subt_comb(Tail, NTail).

subt_comb1([M|Tail], N, [NM|Tail]):-
  M > N,
  NM is M - N.
subt_comb1([N|Tail], N, Tail).
subt_comb1([M|Tail], N, [M|NTail]):-
  subt_comb1(Tail, N, NTail).

Sample:

?- subt_comb([1,2,3], Y).
Y = [1, 3] ;
Y = [2, 2] ;
Y = [1, 1, 2] ;
Y = [1, 1] ;
false.

Answer 2

Here's an alternative solution which uses more fundamental operations. Like @gusbro's solution, it breaks the problem down into (1) examining each element in the list as a range value for reduction, and (2) reducing one more element in the rest of the list based upon the current value in the range defined in (1).

reduce([H|T], R) :-
    reduce_by([H|T], H, R).   % Reduce the list [H|T] by H yielding R
reduce([H|T], [H|R]) :-
    reduce(T, R).             % Do the same for the rest of the list

% reduce_by(L, X, R) reduces two elements in L by each value in the range 1 to X
reduce_by([X|T], X, R) :-
    reduce_once(T, X, R).     % Drop the element if diff is 0, reduce one more from rest
reduce_by([H|T], X, [Y|R]) :-
    H > X,
    Y is H - X,               % reduce current element by X, reduce one more from rest
    reduce_once(T, X, R).
reduce_by(L, X, R) :-
    X1 is X - 1,              % decrement reduction amount and reduce by that amount
    X1 > 0,
    reduce_by(L, X1, R).

% reduce_once(L, X, R) finds one element in L which is >= X and reduces it, else fails
reduce_once([X|T], X, T).     % same value, it's just removed (difference is 0)
reduce_once([H|T], X, [Y|T]) :-
    H > X,                    % reduce the value by X if we can
    Y is H - X.
reduce_once([H|T], X, [H|R]) :-
    reduce_once(T, X, R).     % skip this value and reduce a different value

Results:

| ?- reduce([1,2,3], L).

L = [1,3] ? a

L = [2,2]

L = [1,1]

L = [1,1,2]

no
| ?-

There's a key difference in Prolog versus when programming in Java or C# or other procedural languages. Prolog, through backtracking, will attempt to find all instantiations of the arguments that will make a predicate succeed. See this answer for further details. When writing Prolog predicates (or rules), you need to think about how to state the rules such that they succeed for cases that you want them to. Prolog will do all the work through backtracking to iterate through the all of the possible solutions to success.

For example, in the case of reduce_once, we have one clause that reads:

reduce_once([X|T], X, T).

So this will succeed as long as the arguments can be unified with the inputs. Specifically, a query such as reduce_once([1,2,3], 1, T). will succeed with T = [2,3]. But then once it succeeds, Prolog sees there are other rules for the same predicate, and will attempt those as well. Thus, reduce_once([1,2,3], 1, [1|R]) :- reduce_once([2,3], 1, R). will be executed, etc.