3

在 Prolog 中，我必须想办法将两个已经排序的列表组合成一个排序列表。换句话说：我必须从 2 个列表中比较头部并将最小的添加到新列表中。我想我已经走得很远了，但不知何故它就是行不通，我不知道为什么不行。顺便说一句，我没有收到任何错误。它只是false回馈。

所以，我希望有人能告诉我我做错了什么。

sort([],L,L).
sort(L,[],L).
sort([Head1|Tail1],[Head2|Tail2],L) :- 
    Head1 < Head2 -> append([Head1],L,L2), sort(Tail1,[Head2|Tail2],L2) ; 
    Head1 > Head2 -> append([Head2],L,L2), sort([Head1|Tail1],Tail2,L2) ; 
    Head1 == Head2 -> append([Head1],L,L2), append([Head2],L2,L3), 
                                            sort(Tail1,Tail2,L3).
4

3 回答 3

5

您应该稍微简化一下代码：

sort([],L,L).
sort(L,[],L).
sort([Head1|Tail1], [Head2|Tail2], L) :- 
    Head1 < Head2 -> L = [Head1|R], sort(Tail1,[Head2|Tail2],R) ;
    Head1 > Head2 -> L = [Head2|R], sort([Head1|Tail1],Tail2,R) ;
    L = [Head1,Head2|R], sort(Tail1,Tail2,R).

测试：

?- sort([1,2,4,5,18],[1,3,5,10],R).
R = [1, 2, 3, 4, 5, 10, 18] .

命名这样的谓词排序确实会产生误导，合并会更好....

edit L = [Head1,Head2|R]而不是L = [Head1|R]where Head1=Head2 （之前的测试失败）背离了 sort/2 Prolog 语义，它删除了重复项。

于 2012-10-03T17:57:41.963 回答
2

在 SWI Prolog 中有一个merge/3内置的谓词可以做到这一点。所以你不应该把你的谓词称为“排序”；它不是。这是“合并”。

接下来，让我们阅读您的定义。

merge([H1|T1], [H2|T2], L) :-

意思是，合并两个列表会产生合并的列表L。到目前为止，一切都很好。

    H1 < H2 -> append([H1],L,L2), merge(T1,[H2|T2],L2)

意味着，如果H1 < H2，在答案列表 L前加上give ，H1这L2是合并的结果……等等，什么？那有意义吗？

Prolog 不是基本的。我们写的不是“做”事情的“命令” （嗯，它们是，但以一种迂回的方式）。如果我们想说那H1是 的头部元素L，我们说：

               L = [H1|L2],        merge(T1,[H2|T2],L2) 
        %% or: append([H1],L2,L),

等等。现在这是有道理的。:)

于 2012-10-03T17:27:36.867 回答
1

从您问题中的代码来看，您正在合并排序的数字列表。如果这些数字都是整数并且您的 Prolog 系统提供，请考虑使用此处提供的代码。为什么？

  • 该实现保留了。
  • 代码是单调的，使其健壮和灵活：即使在处理非地面数据时，也总是能得到逻辑上合理的答案。
  • 主谓词sorted1_sorted2_merged/3表现得像一个真实的关系。
  • 与 builtin 不同sort/2，此代码保留所有重复项（完全相同的多重性）。
  • 关于要合并的列表中的相等项目，它的行为是合理的：输入#1 中的项目等于输入#2 中的某些项目，然后是合并结果中的项目。
  • 从某种意义上说，该实现是有效的，它不会留下无用的选择点，如sorted1_sorted2_merged([1,3,5],[2,4,5,6],Zs).

事不宜迟......这是代码：

:- use_module(library(clpfd)).

sorted1_sorted2_merged([]    ,Ys,Ys).
sorted1_sorted2_merged([X|Xs],Ys,Zs) :-
   sorted2_hd1_tl1_merged(Ys,X,Xs,Zs).

hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs) :-
   zcompare(Op,X,Y),
   op_hd1_tl1_hd2_tl2_merged(Op,X,Xs,Y,Ys,Zs).

sorted1_hd2_tl2_merged([]    ,Y,Ys,[Y|Ys]).
sorted1_hd2_tl2_merged([X|Xs],Y,Ys,Zs) :- 
   hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs).

sorted2_hd1_tl1_merged([]    ,X,Xs,[X|Xs]).
sorted2_hd1_tl1_merged([Y|Ys],X,Xs,Zs) :-
   hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs).

op_hd1_tl1_hd2_tl2_merged(<,X,Xs,Y,Ys,[X|Zs]) :-
   sorted1_hd2_tl2_merged(Xs,Y,Ys,Zs).
op_hd1_tl1_hd2_tl2_merged(=,X,Xs,Y,Ys,[X|Zs]) :- 
   sorted1_hd2_tl2_merged(Xs,Y,Ys,Zs).
op_hd1_tl1_hd2_tl2_merged(>,X,Xs,Y,Ys,[Y|Zs]) :- 
   sorted1_hd2_tl2_merged(Ys,X,Xs,Zs).

关于一些查询！第一的：

?- sorted1_sorted2_merged([1,3,4,6],[2,4,5,5,7],Xs).
Xs = [1,2,3,4,4,5,5,6,7].         % succeeds deterministically

它是否也适用于“其他方向”？

?- sorted1_sorted2_merged([1,3,4,6],Ys,[1,2,3,4,4,5,5,6,7]).
Ys = [2,4,5,5,7] ;                % succeeds, but leaves behind choicepoint
false.

?- sorted1_sorted2_merged(Xs,[2,4,5,5,7],[1,2,3,4,4,5,5,6,7]).
Xs = [1,3,4,6] ;                  % succeeds, but leaves behind choicepoint
false.

最后，一个非常普遍的用法：

?- sorted1_sorted2_merged(Xs,Ys,[0,1,2,3]).
Xs = [       ], Ys = [0,1,2,3] ;
Xs = [0,1,2,3], Ys = [       ] ;
Xs = [0      ], Ys = [  1,2,3] ;
Xs = [0,1    ], Ys = [    2,3] ;
Xs = [0,1,2  ], Ys = [      3] ;
Xs = [0,1,  3], Ys = [      2] ;
Xs = [0,  2,3], Ys = [      1] ;
Xs = [0,    3], Ys = [  1,2  ] ;
Xs = [0,  2  ], Ys = [  1,  3] ;
Xs = [  1,2,3], Ys = [0      ] ;
Xs = [    2,3], Ys = [0,1    ] ;
Xs = [      3], Ys = [0,1,2  ] ;
Xs = [    2  ], Ys = [0,1,  3] ;
Xs = [  1    ], Ys = [0,  2,3] ;
Xs = [  1,2  ], Ys = [0,    3] ;
Xs = [  1,  3], Ys = [0,  2  ] ;
false.
于 2015-05-17T12:23:06.197 回答