文字ソート

「文字ソート」の編集履歴(バックアップ)一覧はこちら

文字ソート」(2014/05/09 (金) 13:18:23) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

表示オプション

横に並べて表示:
変化行の前後のみ表示: