Prolog ищет возможную комбинацию для вычитания 2 элементов из списка

Вот альтернативное решение, которое использует более фундаментальные операции. Как и решение @gusbro, оно разбивает проблему на (1) проверку каждого элемента в списке как значение диапазона для сокращения и (2) уменьшение еще одного элемента в остальной части списка на основе текущего значения в определенном диапазоне. в 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

Полученные результаты:

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

L = [1,3] ? a

L = [2,2]

L = [1,1]

L = [1,1,2]

no
| ?-

Существует ключевое отличие Пролога от программирования на Java, C# или других процедурных языках. Пролог посредством поиска с возвратом попытается найти все экземпляры аргументов, которые сделают предикат успешным. Дополнительные сведения см. в этом ответе. При написании предикатов (или правил) Пролога вам нужно подумать о том, как сформулировать правила таким образом, чтобы они выполнялись в тех случаях, в которых вы хотите. Prolog выполнит всю работу путем возврата, чтобы перебрать все возможные решения для достижения успеха.

Например, в случае reduce_once у нас есть одно предложение, которое гласит:

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

Таким образом, это будет успешным, если аргументы могут быть объединены с входными данными. В частности, такой запрос, как reduce_once([1,2,3], 1, T)., будет успешным с T = [2,3]. Но затем, как только это удается, Пролог видит, что для того же предиката существуют другие правила, и также пытается применить их. Таким образом, будет выполнено reduce_once([1,2,3], 1, [1|R]) :- reduce_once([2,3], 1, R). и т.д.

Я бы использовал 2 процедуры.

Первый берет элемент из списка, вычисляет число, равное ему или меньшее, а затем вызывает вторую процедуру для вычитания этого числа из другого элемента в оставшемся списке.

Вы должны позаботиться о пограничных случаях (если вычисленное число равно элементу, то полностью удалите элемент), поэтому я использую другое предложение для этих случаев.

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

Образец:

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