具有约束逻辑编程的排序列表 [英] Ordering lists with constraint logic programming
问题描述
我想知道是否有人可以帮助我解决这个问题:我必须使用 Prolog 和约束逻辑编程来订购一个列表,并且我必须以更有效的方式来完成.
I was wondering if anyone could help me with this problem: I have to order a list using Prolog with Constraing Logic Programming and I must do it with the more efficient way I can.
所以我定义的主要谓词是下一个:
So the main predicate I have defined is the next one:
order(Xs,Ys) :-
same_length(Xs,Ys), /* To determine the list Ys with the Xs' length */
perm(Xs,Ys), /* Permutation */
ordered(Ys), /* Is Ys ordered? */
! .
前面每个辅助谓词的实现如下:
The implementation of each of the previous auxiliary predicates is as follows:
same_length(Xs,Ys) :-
length(Xs,L),
length(Ys,L).
perm([],[]).
perm([X|Xs],Ys) :- elem(X,Ys,Ws), perm(Xs,Ws).
ordered([]).
ordered([_]).
ordered([X,Y|Xs]) :- X =< Y, ordered([Y|Xs]).
elem(X,[X|Ys],Ys).
elem(X,[Y|Ws],[Y|Zs]) :- elem(X,Ws,Zs).
我已经证明了我制作的程序并且它有效!但是我不知道是否可以提高效率,如果可以,我该怎么做(我正在阅读 这个旧线程在这里).我应该添加或修改任何约束吗?
I have proved the program I made and it works! But I don't know if it is possible to improve the efficiency, and if it is, how can I do it (I was reading this old thread here). Should I add or modify any of the constraints?
谢谢!
推荐答案
same_length/2
的定义不会经常终止.相反,考虑
Your definition of same_length/2
will not terminate very often. Instead, consider
same_length([],[]).
same_length([_|Xs], [_|Ys]) :-
same_length(Xs, Ys).
同样,使用 library(lambda)代码>
使用
equally, using library(lambda)
use
... maplist(\_^_^true,Xs, Ys), ...
代替
... same_length(Xs, Ys), ...
您似乎想通过首先声明列表是有序的,然后才搜索排列来重新制定排序.以下适用于 SICStus、SWI、YAP.
It seems you want to reformulate sorting by stating first, that the list is ordered, and only then searching for a permutation. Below works in SICStus, SWI, YAP.
ordered2([]).
ordered2([_]).
ordered2([X,Y|Xs]) :-
when((nonvar(X),nonvar(Y)),
( X =< Y, ordered2([Y|Xs]) )).
list_sorted2(Xs,Ys) :-
maplist(\_^_^true,Xs,Ys),
ordered2(Ys),
perm(Ys,Xs).
请注意 perm/2 中的参数现在被交换了!使用 SWI:
Please note that the arguments in perm/2 are now exchanged! Using SWI:
?- time(order([10,9,8,7,6,5,4,3,2,1],Xs)).
% 38,434,099 inferences, 10.655 CPU in 11.474 seconds (93% CPU, 3607101 Lips)
?- time(list_sorted2([10,9,8,7,6,5,4,3,2,1],Xs)).
% 50,139 inferences, 0.023 CPU in 0.032 seconds (72% CPU, 2205620 Lips)
这篇关于具有约束逻辑编程的排序列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!