t_wの輪郭

Feedlyでフォローするボタン

あれ

2024/5/15 7:38:00

Prologだと6行でクイックソートがかけるのヤバすぎる。 

qsort([], []).
qsort([X], [X]).
qsort([X | L], L1) :- separate(X, L, UpperList, LowerList), qsort(UpperList, UpperListSorted), qsort(LowerList, LowerListSorted), flatten([LowerListSorted, [X], UpperListSorted], L1).
separate(X, [], [], []).
separate(X, [Y | L], [Y | UpperList], LowerList) :- X =< Y, separate(X ,L, UpperList, LowerList).
separate(X, [Y | L], UpperList, [Y | LowerList]) :- X > Y, separate(X ,L, UpperList, LowerList).

memberを使えばseparateをもう1行減らせそう。と思ったが、上手くいかなかった。

あれ

2024/5/15 1:07:00

Prologだと4行のコードでソート作れるのヤバすぎる。 

% 空リストは昇順
ordered([]).
% 要素が一つのリストは昇順
ordered([_]).  
% 先頭2つの要素が昇順 かつ 2番目以降の要素が昇順のリストは昇順
ordered([X, Y|T]) :- X =< Y, ordered([Y|T]).
% 全順列のうち、昇順になっているものは、ソートされている
mysort(L, L1) :- permutation(L, L1), ordered(L1).