文字ソート


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

az-prologのフォルダの中にクイックソートのサンプルプログラムがありますが、
ここでは文字列を比較してAから順にソートする文字列ソートプログラムを作成してみましょう。

test:-
L=["BBB","ABC","ACA","ACB","ACC","CBB","CBC","CCA","CCB","CCC",
   "ABB","BBC","BCA","BCBD","BCBE","BCC","AAA","AAB","AAC","ABA",
   "CAA","CAB","CAC","CBA","BAA","BAB","BAC","BBA"],
strsort(L,R),flats(R,X),write(X).

strsort(L,U):-s_sort(L,[],R), %write('R'=R),nl,
strsort2(R,T-T,U). %,write('U'=U),nl.
 
strsort2([],_,[]):-!.
strsort2([[A]],_,[A]):-!.
strsort2([[A]|L],_,[A|R]):-!,strsort(L,R). %write([A,R]),nl.
strsort2([[A|AL]|[]],T-[AL],C):-!,
strsort(T,R),strsort3(A,R,C). %,write('C'=C),nl.
strsort2([[A|L],[A|M]|N],T-[L|S],U):-strsort2([[A|M]|N],T-S,U).
strsort2([[A|L],[B|M]|N],T-[L],D):-strsort(T,R),strsort3(A,R,C), %write('C'=C),nl,
strsort2([[B|M]|N],X-X,U),append(C,U,D). %,write(C),nl.

strsort3(A,[],[]):-!.
strsort3(A,[B|L],[[A,B]|M]):-strsort3(A,L,M).
strsort3(A,[[B|BL]|L],[[A,B|BL]|M]):-strsort3(A,L,M).

s_sort([],L,L).
s_sort([A|L],R,Z):-p(L,A,B,C),
% write('A'=A),nl,
% write('L'=L),nl,
% write('B'=B),nl,
% write('C'=C),nl,
 s_sort(B,[A|X],Z),s_sort(C,R,X).

p([],_,[],[]).
p([[X|XL]|L],[A|AL],[[X|XL]|B],C):-X=<A,!,p(L,[A|AL],B,C).
p([X|L],A,B,[X|C]):-p(L,A,B,C).

flats([],[]):-!.
flats([A|L],[B|M]):-flat(A,B),flats(L,M).
flat(A,B):-flat(A,[],B),!.
flat([],X,X).
flat([A|L],R,Z):-flat(A,X,Z),flat(L,R,X).
flat(A,X,[A|X]).

確認してみましょう。
| ?-test.
[[65,65,65],[65,65,66],[65,65,67],[65,66,65],[65,66,66],[65,66,67],[65,67,65],[65,67,66],
[65,67,67],[66,65,65],[66,65,66],[66,65,67],[66,66,65],[66,66,66],[66,66,67],[66,67,65],
[66,67,66,68],[66,67,66,69],[66,67,67],[67,65,65],[67,65,66],[67,65,67],[67,66,65],
[67,66,66],[67,66,67],[67,67,65],[67,67,66],[67,67,67]]

ここまで書きましたが、実はオペレータ@を使ったほうがもっと簡単にできます。
そちらはここでは書かないので、ご興味があれば作ってみてください。