% permutacija 
perm([],[]).
perm([H|T],R):-perm(T,R1),ubacin(H,R1,R). 

% drvo obilaska za 1->[2,3,4] se nalazi u dokumentu izvodjenje.pdf
ubacin(X,[],[X]).
ubacin(X,[H|T],[X,H|T]).
ubacin(X,[H|T],[H|R1]):-ubacin(X,T,R1).

/*
4 ?- 
|    perm([1,2,3,4],X).
X = [1, 2, 3, 4] ;
X = [2, 1, 3, 4] ;
X = [2, 3, 1, 4] ;
X = [2, 3, 4, 1] ;
X = [1, 3, 2, 4] ;
X = [3, 1, 2, 4] ;
X = [3, 2, 1, 4] ;
X = [3, 2, 4, 1] ;
...
*/

komb([],K,[]):-K>0,fail.
/* ako se oznaka nigde ne koristii nema nikakva
 ogranicenje mozemo
 staviti _ umesto naziva */
komb([],0,[]).
% pravilo za generisanje kombinacije koja ukljucuje glavu
komb([H|T],K,[H|R]):-K1 is K-1,komb(T,K1,R).
% ovo za komb. koja ne ukljucuje glavu
komb([_|T],K,R):-komb(T,K,R).

var1(L,K,V):-komb(L,K,Komb),perm(Komb,V).

%drugi nacin je slozeniji
var2([],K,[]):-K>0,fail.
var2([],0,[]).
var2([H|T],K,R):-K1 is K-1,var2(T,K1,R1),ubacin(H,R1,R).
var2([_|T],K,R):-var2(T,K,R).


naivnisort(L,P):-perm(L,P),sortirana(P).
sortirana([]).
sortirana([X]).
sortirana([H1,H2|T]):-H1=<H2,sortirana([H2|T]).

isort([],[]).
isort([H|T],S):-isort(T,S1),ubacis(H,S1,S).
% ubaci uredjeno (sortirano)
ubacis(X,[],[X]).
%ubacis(X,[H|T],[X,H|T]):-X=<H.
%ubacis(X,[H|T],[H|S]):-X>H,ubacis(X,T,S).
% alternativno sa cut operatorom ne moramo
% da pisemo X>H u drugom predikatu, jer 
% kada stavimo cut operator kod prvog, cim 
% on uspe drugi predikat se nece ni pokusavati
ubacis(X,[H|T],[X,H|T]):-X=<H,!.
ubacis(X,[H|T],[H|S]):-ubacis(X,T,S).

msort([],[]).
msort([X],[X]).
msort(N,S):-podeli(N,L,R),msort(L,L1),msort(R,R1),
objedini(L1,R1,S).

% delimo tako sto prvi stavljamo u prvu particiju
% drugi u drugu pri cemu su particije dobijene
% vec rekurzivno podelom repa
podeli([],[],[]).
podeli([X],[X],[]).
podeli([H1,H2|T],[H1|T1],[H2|T2]):-podeli(T,T1,T2).

/*
npr. ako objedinjujemo [1,3,5,7] i [5,6,7,8,9]
znamo da 1 prethodi svima pa mozemo 
rekurzivno da objedinimo [3,5,7] sa [5,6,7,8,9]
i dodamo 1 na pocetak tako objedinjene liste
*/
objedini(L,[],L).
objedini([],L,L).
objedini([H1|T1],[H2|T2],[H1|R]):-
H1<H2,objedini(T1,[H2|T2],R).
objedini([H1|T1],[H2|T2],[H2|R]):-
H1>=H2,objedini([H1|T1],T2,R).