Permutations

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

/* This is much slower and not reversible, but is tail-recursive. And the  */
/*   permutations are produced in a "logical" order.                       */
permute_slow([], []).
permute_slow(Xs, [Y|Ys]):-
  remove(Y, Xs, Zs), permute_slow(Zs, Ys).

/* This is pretty fast and is reversible, that is,                         */
/*   permute_reversible(X, [1,2,3]) instantiates X, on backtracking, to    */
/*   successive permutations of [1,2,3].                                   */
permute_reversible(Xs, Ys):-permute_reversible_1(Xs, Ys, Ys).

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

/* This version, due to Thom Fruehwirth, finds distinct permutations of a  */
/*   list which may have repeated elements.                                */
permute_distinct([], []).
permute_distinct(L, [X|L2]):-
  my_delete(X, L, L1),
  permute_distinct(L1, L2).

my_delete(X, [X|L], L).
my_delete(X, [Y|R], [Y|L]):-my_delete(X, R, L), X \== Y. 

/* parity(Xs, Ys, P) is true if P is the parity of the permutation Xs of   */
/*   Ys.  The value 1 represents an even parity; the value -1 an odd       */
/*   parity.                                                               */
parity(Xs, Ys, P):-
  permute(Xs, Ys),
  sign_of_product_of_differences(Xs, 1, D),
  sign_of_product_of_differences(Ys, 1, E),
  P is 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 is D0 * (Y - X) // abs(Y - X),
  sign_of_product_of_differences_1(Xs, Y, D1, D).

LPA Index     Home Page