带约束逻辑编程的订货单 [英] Ordering lists with constraint logic programming

问题描述

我想知道是否有人可以帮助我解决这个问题:我必须使用Prolog和Constraing Logic Programming来订购列表，而我必须以更有效的方式来做到这一点.

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屋！