在列表中使用贪心算法搜索

Question

给定一个正整数 Items 的列表，其元素保证按升序排序，以及一个正整数 Goal，Output 是从项目中取出的三个元素 [A,B,C] 的列表，这些元素加在一起达到目标。输出必须按该顺序（升序）出现在项目列表中。

例如：

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

有人帮我找到了这段代码但它给了我单例变量：[Input,Items]，它没有用虽然我不太确定这是否是贪婪算法搜索？

 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

警告是因为代码从不查看输入列表中的数字。不这样做，它怎么能行得通？

although iam not quite sure if this is a greedy algorithm

是先大后小吗？我认为 permutation 不会那样做。

Answer 2

clpfd 方法：

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

将数字列表转换为域有点争论，然后说 [A,B,C] 必须在数字列表中，必须是不同的数字，必须按降序排列，必须总和为目标，clpfd 求解器应努力使 A、B、C 的值最大化。（如果列表可以包含多个相同的值，如 [5,5,5,3,2，这可能不起作用]).

例如

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

Answer 3

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

结果swi-prolog（注意效率）：

?- 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

重述问题陈述：

鉴于我有

一个[source]正整数列表，其元素保证按升序排序，并且
表示目标值的正整数。

我要找

总和为目标值的源列表元素的有序子集

最简单的方法通常是最简单的（也是最通用的）：

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

这将找到任意数量的列表元素的组合总和达到目标值。它会从左到右找到它们，所以

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

将在回溯中依次找到

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       ]

如果您想更改顺序以便它首先找到最大值，只需反转 sum_of/3 中第 2 条和第 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) .

现在它将 return 相同的一组解决方案，只是顺序相反，从 [4,6] 开始到 [1,2,3,4] 结束。

一旦解决了一般问题，将其限制为指定数量的元素就很简单了，例如：

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

并仅获取总和为目标值的 3 元素子集：

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

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

在列表中使用贪心算法搜索

using greedy algorithm search in lists

prolog

swi-prolog