Prolog 搜索从列表中减去 2 个元素的可能组合

这是本页的扩展问题。Prolog 可能删除列表中的元素 https://stackoverflow.com/questions/33652059/prolog-possible-removal-of-elements-in-a-list/33652274?noredirect=1#comment55118895_33652274

例如，对于列表 X = [1,2,3]，我可以像下面这样进行减法：

第一个/第二个元素减 1，X 变为 [1-1, 2-1, 3] = [0, 1, 3] = [1, 3]

从第一个/第三个元素减 1：X 变为 [2, 2]

从第二个/第三个元素减 1：X 变为 [1, 1, 2]

从第二个/第三个元素中减去 2：X 变为[1, 1]

因此，它总是减去 2 个元素，并且使用相同的数字，但始终是实数。有人对此有什么想法吗？

这看起来更好：

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

在查看了 lurker 和 gusbro 的解决方案后，我创建了类似的东西。

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.

这是使用更基本操作的替代解决方案。与@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

Results:

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

L = [1,3] ? a

L = [2,2]

L = [1,1]

L = [1,1,2]

no
| ?-

Prolog 与 Java 或 C# 或其他过程语言编程有一个关键的区别。 Prolog 通过回溯，尝试找到使谓词成功的参数的所有实例。看这个答案 https://stackoverflow.com/questions/33692335/prolog-permutation-code-understanding#33694081了解更多详情。在编写 Prolog 谓词（或规则）时，您需要考虑如何陈述规则，以便它们在您希望的情况下成功。 Prolog 将通过回溯来完成所有工作，以迭代所有可能的成功解决方案。

例如，在以下情况reduce_once，我们有一个子句：

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

因此，只要参数可以与输入统一，这就会成功。具体来说，诸如以下的查询reduce_once([1,2,3], 1, T).将会成功T = [2,3]。但一旦成功，Prolog 就会发现同一谓词还有其他规则，并且也会尝试这些规则。因此，reduce_once([1,2,3], 1, [1|R]) :- reduce_once([2,3], 1, R).将被处决等