%%% FCP Ex. 4.3 %%%

:-lib(ic).


%%%%%%% 4.3 a) %%%%

insert(E,List,[E|List]).
insert(E,[H|T],[H|List]) :- insert(E,T,List).


permutation([],[]).
permutation([H|T],Perm) :- samelength([H|T],Perm),
	insert(H,Perm1,Perm), permutation(T,Perm1).


samelength([],[]).
samelength([_|T1],[_|T2]) :- samelength(T1,T2).


%%%%%%% 4.3 b) %%%%

sorted([]).
sorted([_]).
sorted([X,Y|R]):- X#=<Y, sorted([Y|R]).

permsort(L,SL) :- permutation(L,SL), sorted(SL).


%%%%%%% 4.3 c) %%%%

permsort2(L,SL) :- samelength(L,SL), 
sorted(SL), permutation(L,SL).