给定一个由正整数Items组成的列表，其元素保证按升序排序，以及一个正整数Goal，输出是一个由三个元素[a,B,C]组成的列表，这些元素之和为Goal。Output必须按该顺序出现在items列表中(升序)。
,
?- 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).
一个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]
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).
有人帮助我达到这个到这个代码，但它给了我单例变量:[Input,Items]，它不起作用
出现警告是因为代码从未查看Input列表中的数字。如果不这样做，它怎么可能工作呢?
虽然我不太确定这是否是一个贪婪算法
是先取最大的东西吗?我不认为permutation会那样做。
使用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]].
重述问题陈述:
给定
- 一个正整数列表，其元素保证按升序排序，
- 指示目标值的正整数。
我想找到
- 源列表中求和为目标值的元素的有序子集
最简单的方法往往是最简单的(也是最通用的):
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) .
现在它将返回相同的一组溶液，只是顺序相反，从[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