A fun Prolog snippet

interesting.pl

% select(X,HasXs,OneLessXs) deletes a single X from HasXs
select(X, [X|Xs], Xs).
select(X, [Y|Ys], [Y|Zs]) <- select(X, Ys, Zs).

% insert(X,OneLessXs, HasXs) inserts X into OneLessXs at a non-deterministic position
insert(X, Ys, Zs) <- select(X, Zs, Ys).

% permutation1(Input, Output)
% non-deterministically select the head of the output, permute the remaining input and use as the tail
permutation1(Xs, [Z|Zs]) <- select(Z,Xs,Ys), permutation(Ys,Zs).
permutation1([], []).

% permutation2(Input,Output)
% permutate the tail of the input, then insert the head of the input into a non-deterministic position
permutation2([X|Xs], Zs) <- permutation(Xs,Ys), insert(X,Ys,Zs).
permutation2([], []).