Zdroj



% setrideny(S)
setrideny([]).
setrideny([_]).
setrideny([A,B|C]) :- A=<B, setrideny([B|C]).



% predikat backtrackujici pres vsechny permutace
% (kazda moznost prave jednou,
%  prvky vstupu povazujeme za ruzne)
%permut(+Seznam, -PermutovanySeznam)
permut([], []).
permut(L, [X|P]) :- select2(X, L, R), permut(R, P).

select2(X,[X|V],V).
select2(X,[P|Z],[P|V]) :- select2(X,Z,V).


%% Cil: mergesort

% split2(+List, -Odd, -Even)
split2([], [], []).
split2([H], [H], []).
split2([H,I|T], [H|O], [I|E]) :- split2(T, O, E).

% merdz(+List1, +List2, -List)
merdz(L, [], L).
merdz([], L, L).
merdz([H1|T1],[H2|T2],[H1|T]) :- H1<H2, merdz(T1,[H2|T2],T).
merdz([H1|T1],[H2|T2],[H2|T]) :- H2=<H1, merdz([H1|T1],T2,T).

% mergesort(+Vstup, -Vystup)
mergesort([], []).
mergesort([X],[X]). % vvv obrana proti cykleni
mergesort(X, Y) :- X=[_,_|_], split2(X, X1, X2),
	mergesort(X1,Y1), mergesort(X2,Y2),
	merdz(Y1,Y2,Y).

Dotazy


?- append(A,B,[1,2,3,4]).
A = [],
B = [1, 2, 3, 4] ;
A = [1],
B = [2, 3, 4] ;
A = [1, 2],
B = [3, 4] ;
A = [1, 2, 3],
B = [4] ;
A = [1, 2, 3, 4],
B = [] ;
false.

?- permut([1,2,3,4,5,6],X).
X = [1, 2, 3, 4, 5, 6] ;
X = [1, 2, 3, 4, 6, 5] ;
X = [1, 2, 3, 5, 4, 6] ;
X = [1, 2, 3, 5, 6, 4] ;
X = [1, 2, 3, 6, 4, 5] ;
X = [1, 2, 3, 6, 5, 4] ;
X = [1, 2, 4, 3, 5, 6] ;
X = [1, 2, 4, 3, 6, 5] ;
X = [1, 2, 4, 5, 3, 6] ;
X = [1, 2, 4, 5, 6, 3] ;
X = [1, 2, 4, 6, 3, 5] ;
X = [1, 2, 4, 6, 5, 3] ;
X = [1, 2, 5, 3, 4, 6] ;
X = [1, 2, 5, 3, 6, 4] ;
X = [1, 2, 5, 4, 3, 6] ;
X = [1, 2, 5, 4, 6, 3] ;
X = [1, 2, 5, 6, 3, 4] ;
X = [1, 2, 5, 6, 4, 3] ;
X = [1, 2, 6, 3, 4, 5] ;
X = [1, 2, 6, 3, 5, 4] ;
X = [1, 2, 6, 4, 3, 5] ;
X = [1, 2, 6, 4, 5, 3] ;
X = [1, 2, 6, 5, 3, 4] ;
X = [1, 2, 6, 5, 4, 3] ;
X = [1, 3, 2, 4, 5, 6] ;
X = [1, 3, 2, 4, 6, 5] ;
X = [1, 3, 2, 5, 4, 6] . % další řešení odmítnuta

?- mergesort([9,7,2,8,3,8,1,6,7],X).
X = [1, 2, 3, 6, 7, 7, 8, 8, 9] ;
false.