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).
Turbo Prolog Index
Home Page