Prolog搜索从列表中减去2个元素的可能组合 [英] Prolog search for possible combination for subtracting 2 elements from a list

问题描述

这是此页面的扩展问题. 序言可能会删除列表中的元素

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

例如，对于列表X = [1,2,3]，我可以像这样减去:

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

从1st/2nd元素中减去1，X变成[1-1，2-1，3] = [0，1，3] = [1，3]

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

从第1个/第3个元素中减去1:X变成[2，2]

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

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

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

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

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

因此，它总是减去2个元素，并且具有相同的数目，但始终为实数.有人对此有任何想法吗?

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

这看起来更好:

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

在研究了潜伏者和gusbro的解决方案之后，我创建了类似的东西.

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.

推荐答案

这是使用更多基本操作的替代解决方案.就像@gusbro的解决方案一样，它将问题分解为(1)将列表中的每个元素作为减少的范围值进行检查，以及(2)根据定义的范围中的当前值，在列表的其余部分中再减少一个元素在(1)中.

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

结果:

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

L = [1,3] ? a

L = [2,2]

L = [1,1]

L = [1,1,2]

no
| ?-

与使用Java或C#或其他过程语言进行编程时，Prolog有一个关键区别.通过回溯，Prolog将尝试查找使谓词成功的参数的所有实例.有关更多详细信息，请参见此答案.在编写Prolog谓词(或规则)时，您需要考虑如何陈述规则，以使规则在需要的情况下成功. Prolog将通过回溯完成所有工作，以遍历所有可能的成功解决方案.

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.

例如，对于reduce_once，我们有一个子句显示为:

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

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

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.

这篇关于Prolog搜索从列表中减去2个元素的可能组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！