3

Prologでは、すでにソートされている2つのリストを1つのソートされたリストに結合する方法を理解する必要があります。つまり、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] .

このような述語の並べ替えに名前を付けるのは本当に誤解を招く可能性があります。マージの方がはるかに優れています。

Head1 = Head2（前のテストに失敗した）がsort / 2 Prologセマンティクスから逸脱するL = [Head1,Head2|R]代わりに編集し、重複を削除します。L = [Head1|R]

于 2012-10-03T17:57:41.963 に答える
2

SWI Prologにmerge/3は、まさにそれを行う組み込みの述語があります。したがって、述語を「ソート」と呼ぶべきではありません。そうではありません。それは「マージ」です。

次に、あなたの定義を読みましょう。

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

つまり、2つのリストをマージすると、マージされたリストが生成されますL。ここまでは順調ですね。

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

つまり、場合によっては、回答リストH1 < H2の前に「gives 」を付けます。これは、マージの結果です...待って、何ですか？それは理にかなっていますか？ LH1L2

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は実際の関係のように動作します。
  • 組み込みとは異なりsort/2、このコードはすべての重複を（まったく同じ多重度で）保持します。
  • マージされるリスト内の等しいアイテムに関しては、合理的に動作します。入力＃2の一部のアイテムと等しい入力＃1のアイテムは、マージされた結果のアイテムよりも前になります。
  • 実装は、のような目標を持つ無駄な選択ポイントを残さないという意味で効率的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 に答える