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