list Prolog，在列表中找到最小值
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3965054/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Prolog, find minimum in a list
提问by Roy
in short: How to find min value in a list? (thanks for the advise kaarel)
简而言之：如何在列表中找到最小值？（感谢 kaarel 的建议）
long story:
很长的故事：
I have created a weighted graph in amzi prolog and given 2 nodes, I am able to retrieve a list of paths. However, I need to find the minimum value in this path but am unable to traverse the list to do this. May I please seek your advise on how to determine the minimum value in the list?
我在 amzi prolog 中创建了一个加权图，并给出了 2 个节点，我能够检索路径列表。但是，我需要在此路径中找到最小值，但无法遍历列表来执行此操作。我可以就如何确定列表中的最小值征求您的意见吗？
my code currently looks like this:
我的代码目前看起来像这样：
arc(1,2). arc(2,3). arc(3,4). arc(3,5). arc(3,6). arc(2,5). arc(5,6). arc(2,6). path(X,Z,A) :- (arc(X,Y),path(Y,Z,A1),A is A1+1;arc(X,Z), A is 1).
thus, ' keying findall(Z,path(2,6,Z),L).' in listener allows me to attain a list [3,2,2,1]. I need to retrieve the minimum value from here and multiply it with an amount. Can someone please advise on how to retrieve the minimum value? thanks!
因此，'键入 findall(Z,path(2,6,Z),L).' 在听众中，我可以得到一个列表 [3,2,2,1]。我需要从这里检索最小值并将其乘以一个数量。有人可以就如何检索最小值提出建议吗？谢谢！
回答by mat
It is common to use a so-called "lagged argument" to benefit from first-argument indexing:
通常使用所谓的“滞后参数”来从第一参数索引中受益：
list_min([L|Ls], Min) :-
list_min(Ls, L, Min).
list_min([], Min, Min).
list_min([L|Ls], Min0, Min) :-
Min1 is min(L, Min0),
list_min(Ls, Min1, Min).
This pattern is called a fold(from the left), and foldl/4, which is available in recent SWI versions, lets you write this as:
这种模式称为折叠（从左侧开始），并且foldl/4在最近的 SWI 版本中可用，让您可以将其写为：
list_min([L|Ls], Min) :- foldl(num_num_min, Ls, L, Min).
num_num_min(X, Y, Min) :- Min is min(X, Y).
Notice though that this cannot be used in all directions, for example:
请注意，这不能用于所有方向，例如：
?- list_min([A,B], 5).
is/2: Arguments are not sufficiently instantiated
If you are reasoning about integers, as seems to be the case in your example, I therefore recommend you use CLP(FD) constraints to naturally generalize the predicate. Instead of (is)/2, simply use (#=)/2and benefit from a more declarative solution:
如果您正在推理integers，就像您的示例中的情况一样，因此我建议您使用 CLP(FD) 约束来自然地概括谓词。而不是(is)/2，只需使用(#=)/2更具声明性的解决方案并从中受益：
:- use_module(library(clpfd)).
list_min([L|Ls], Min) :- foldl(num_num_min, Ls, L, Min).
num_num_min(X, Y, Min) :- Min #= min(X, Y).
This can be used as a true relation which works in all directions, for example:
这可以用作适用于所有方向的真实关系，例如：
?- list_min([A,B], 5).
yielding:
产生：
A in 5..sup,
5#=min(B, A),
B in 5..sup.
回答by andersoj
回答by Joe Flynn
%Usage: minl(List, Minimum).
minl([Only], Only).
minl([Head|Tail], Minimum) :-
minl(Tail, TailMin),
Minimum is min(Head, TailMin).
The second rule does the recursion, in english "get the smallest value in the tail, and set Minimum to the smaller of that and the head". The first rule is the base case, "the minimum value of a list of one, is the only value in the list".
第二条规则进行递归，用英语“获取尾部的最小值，并将最小值设置为最小值和头部中的较小者”。第一条规则是基本情况，“一个列表的最小值，是列表中的唯一值”。
Test:
测试：
| ?- minl([2,4,1],1).
true ?
yes
| ?- minl([2,4,1],X).
X = 1 ?
yes
You can use it to check a value in the first case, or you can have prolog compute the value in the second case.
您可以使用它来检查第一种情况下的值，或者您可以让 prolog 计算第二种情况下的值。
回答by CapelliC
SWI-Prolog offers library(aggregate). Generalized and performance wise.
SWI-Prolog 提供库（聚合）。广义和性能明智。
:- [library(aggregate)].
min(L, M) :- aggregate(min(E), member(E, L), M).
edit
编辑
A recent addition was library(solution_sequences). Now we can write
最近添加的是 library( solution_sequences)。现在我们可以写
min(L,M) :- order_by([asc(M)], member(M,L)), !.
max(L,M) :- order_by([desc(M)], member(M,L)), !.
Now, ready for a surprise :) ?
现在，准备好惊喜了 :) ？
?- test_performance([clpfd_max,slow_max,member_max,rel_max,agg_max]).
clpfd_max:99999996
% 1,500,000 inferences, 0.607 CPU in 0.607 seconds (100% CPU, 2470519 Lips)
slow_max:99999996
% 9,500,376 inferences, 2.564 CPU in 2.564 seconds (100% CPU, 3705655 Lips)
member_max:99999996
% 1,500,009 inferences, 1.004 CPU in 1.004 seconds (100% CPU, 1494329 Lips)
rel_max:99999996
% 1,000,054 inferences, 2.649 CPU in 2.648 seconds (100% CPU, 377588 Lips)
agg_max:99999996
% 2,500,028 inferences, 1.461 CPU in 1.462 seconds (100% CPU, 1710732 Lips)
true
with these definitions:
```erlang
:- use_module(library(clpfd)).
clpfd_max([L|Ls], Max) :- foldl([X,Y,M]>>(M #= max(X, Y)), Ls, L, Max).
slow_max(L, Max) :-
select(Max, L, Rest), \+ (member(E, Rest), E @> Max).
member_max([H|T],M) :-
member_max(T,N), ( \+ H@<N -> M=H ; M=N ).
member_max([M],M).
rel_max(L,M) :-
order_by([desc(M)], member(M,L)), !.
agg_max(L,M) :-
aggregate(max(E), member(E,L), M).
test_performance(Ps) :-
test_performance(Ps,500 000,_).
test_performance(Ps,N_Ints,Result) :-
list_of_random(N_Ints,1,100 000 000,Seq),
maplist({Seq}/[P,N]>>time((call(P,Seq,N),write(P:N))),Ps,Ns),
assertion(sort(Ns,[Result])).
list_of_random(N_Ints,L,U,RandomInts) :-
length(RandomInts,N_Ints),
maplist({L,U}/[Int]>>random_between(L,U,Int),RandomInts).
clpfd_max wins hands down, and to my surprise, slow_max/2 turns out to be not too bad...
clpfd_max 胜出，令我惊讶的是，slow_max/2 结果还不错……
回答by TomaDeLosTacos
This is ok for me :
这对我来说没问题：
minimumList([X], X). %(The minimum is the only element in the list)
minimumList([X|Q], M) :- % We 'cut' our list to have one element, and the rest in Q
minimumList(Q, M1), % We call our predicate again with the smallest list Q, the minimum will be in M1
M is min(M1, X). % We check if our first element X is smaller than M1 as we unstack our calls
回答by Daniel Libanori
Solution without "is".
没有“是”的解决方案。
min([],X,X).
min([H|T],M,X) :- H =< M, min(T,H,X).
min([H|T],M,X) :- M < H, min(T,M,X).
min([H|T],X) :- min(T,H,X).
回答by Kaarel
SWI-Prolog has min_list/2:
SWI-Prolog 有min_list/2：
min_list(+List, -Min)
True if Min is the smallest number in List.
Its definition is in library/lists.pl
它的定义在 library/lists.pl
min_list([H|T], Min) :-
min_list(T, H, Min).
min_list([], Min, Min).
min_list([H|T], Min0, Min) :-
Min1 is min(H, Min0),
min_list(T, Min1, Min).
回答by Roy
thanks for the replies. been useful. I also experimented furthur and developed this answer:
感谢您的回复。有用过。我还进一步试验并得出了这个答案：
% if list has only 1 element, it is the smallest. also, this is base case.
min_list([X],X).
min_list([H|List],X) :-
min_list(List,X1), (H =< X1,X is H; H > X1, X is X1).
% recursively call min_list with list and value,
% if H is less than X1, X1 is H, else it is the same.
Not sure how to gauge how good of an answer this is algorithmically yet, but it works! would appreciate any feedback nonetheless. thanks!
不确定如何从算法上衡量这个答案的好坏，但它有效！尽管如此，仍将不胜感激。谢谢！
回答by Adam Stelmaszczyk
Similar to andersoj, but using a cut instead of double comparison:
类似于 andersoj，但使用切割而不是双重比较：
min([X], X).
min([X, Y | R], Min) :-
X < Y, !,
min([X | R], Min).
min([X, Y | R], Min) :-
min([Y | R], Min).
回答by Js Lim
min([Second_Last, Last], Result):-
Second_Last < Last
-> Result = Second_Last
; Result = Last, !.
min([First, Second|Rest], Result):-
First < Second
-> min([First|Rest], Result)
; min([Second|Rest], Result).
Should be working.
应该工作。
