% Sort a list of numbers, i.e.,
% psort(UL,OL) <=> OL is a sorted version of UL
% Example: psort([3,1,4,2],[1,2,3,4]).
% Example: ?- psort([3,1,4,2],L).
%          L = [1,2,3,4]

% A list of sorted if subsequent elements are in order:
sorted([]).
sorted([_]).
sorted([E1,E2|L]) :- E1 =< E2, sorted([E2|L]).

% A permutation of a list:
perm([],[]).
perm(Xs,[E|Ys]) :- select(E,Xs,Zs), perm(Zs,Ys).

% Select some element in a list and the third argument is the remaining list
select(E, [E|Xs], Xs).
select(E, [F|Xs], [F|Ys]) :- select(E,Xs,Ys).

% Overall scheme:
psort(UL,OL) :- perm(UL,OL), sorted(OL).
% Complixity: 10 elements => 10! = 3,628,800 permutations
