#### Permutations

```check_determ
domains
int     = integer
ints    = int*
refint  = integer
refints = reference refint*
predicates
nondeterm permute(ints,ints)
nondeterm permute_slow(ints,ints)
nondeterm permute_very_slow(refints,refints)
nondeterm permute_very_slow_1(refints,refints,refints)
nondeterm even_permutation(ints,ints)
nondeterm odd_permutation(ints,ints)
sign_of_product_of_differences(ints,int,int)
sign_of_product_of_differences_1(ints,int,int,int)
nondeterm remove(int,ints,ints)
nondeterm remove(refint,refints,refints)
clauses

/* permute(Xs, Ys) is true if Ys is a permutation of the list Xs.          */
/* This is fast but not reversible.                                        */
permute([], []).
permute([X|Xs], Ys1):-
permute(Xs, Ys), remove(X, Ys1, Ys).

/* This is slow and not reversible.                                        */
permute_slow([], []).
permute_slow(Xs, [Y|Ys]):-
remove(Y, Xs, Zs), permute_slow(Zs, Ys).

/* This is very slow but reversible, that is, permute_very_slow(X,[1,2,3]) */
/*   instantiates X, on backtracking, to successive permutations of        */
/*   [1,2,3].                                                              */
permute_very_slow(Xs, Ys):-permute_very_slow_1(Xs, Ys, Ys).

permute_very_slow_1([], [], []).
permute_very_slow_1([X|Xs], Ys1, [_|Zs]):-
permute_very_slow_1(Xs, Ys, Zs),
remove(X, Ys1, Ys).

/* even_permutation(Xs, Ys) is true if Ys is an even permutation of Xs.   */
even_permutation(Xs, Ys):-
permute(Xs, Ys),
sign_of_product_of_differences(Xs, 1, D),
sign_of_product_of_differences(Ys, 1, E),
D = E.

/* odd_permutation(Xs, Ys) is true if Ys is an odd permutation of Xs.     */
odd_permutation(Xs, Ys):-
permute(Xs, Ys),
sign_of_product_of_differences(Xs, 1, D),
sign_of_product_of_differences(Ys, 1, E),
D <> E.

sign_of_product_of_differences([], D, D).
sign_of_product_of_differences([Y|Xs], D0, D):-
sign_of_product_of_differences_1(Xs, Y, D0, D1),
sign_of_product_of_differences(Xs, D1, D).

sign_of_product_of_differences_1([], _, D, D).
sign_of_product_of_differences_1([X|Xs], Y, D0, D):-
Y <> X,
D1 = D0 * (Y - X) / abs(Y - X),
sign_of_product_of_differences_1(Xs, Y, D1, D).

/* remove(X, Ys, Zs) is true if Zs is the result of removing one           */
/*   occurrence of the element X from the list Ys.                         */
remove(X, [X|Xs], Xs).
remove(X, [Y|Ys], [Y|Zs]):-
remove(X, Ys, Zs).
```