Resolvability of Affine Planes

This code requires the Affine Planes of Prime Power Order package.

/*
 * A (v,k,lambda) design D is resolvable if D can be partitioned into r
 * collections Di each consisting of b/r = v/k of the blocks and every
 * element of S appears in exactly one block in Di for all i. The subsets
 * Di are called parallel classes.
 */

/* parallel_classes(AffinePlane, ParallelClasses) is true if the Q+1         */
/*   elements of the ParallelClasses form a resolution of the AffinePlane of */
/*   order Q.                                                                */
/* e.g. parallel_classes([[1,2,3],[1,4,7],[1,5,9],[1,6,8],[2,4,9],[2,5,8],   */
/*                        [2,6,7],[3,4,8],[3,5,7],[3,6,9],[4,5,6],[7,8,9]],  */
/*                       [[[1,2,3],[4,5,6],[7,8,9]],                         */
/*                        [[1,4,7],[2,5,8],[3,6,9]],                         */
/*                        [[1,5,9],[2,6,7],[3,4,8]],                         */
/*                        [[1,6,8],[2,4,9],[3,5,7]]]).                       */
parallel_classes([], []).
parallel_classes([Xs|AffinePlane], [[Xs|Yss]|ParallelClasses]):-
  findall(Ys, disjoint_element(AffinePlane, Xs, Ys), Yss),
  delete_all(Yss, AffinePlane, AffinePlane1),
  parallel_classes(AffinePlane1, ParallelClasses).

/* disjoint_element(Xss, Ys, Xs) is true if Xs is an element of Xss such     */
/*   Xs and Ys have no common elements.                                      */
disjoint_element([Xs|_], Ys, Xs):-
  disjoint(Xs, Ys).
disjoint_element([_|Xss], Ys, Xs):-
  disjoint_element(Xss, Ys, Xs).

/* delete_all(Xs, Ys, Zs) is true if Zs is the result of removing the first  */
/*   occurrence of each element of the list Xs from the list Ys.             */
delete_all([], Ys, Ys).
delete_all([X|Xs], Ys, Zs):-efface(Ys, X, Ws), delete_all(Xs, Ws, Zs).

/* disjoint(Xs, Ys) is true if the sets of elements in lists Xs and Ys have  */
/*   no common element.                                                      */
disjoint([], _).
disjoint([X|Xs], Ys):-
  \+ member(X, Ys), 
  disjoint(Xs, Ys).

/* efface(Xs, Y, Zs) is true if Zs is the result of deleting the first       */
/*   occurrence of the element Y from the list Xs.                           */
efface([], _, []).
efface([Y|Xs], Y, Xs):-!.
efface([X|Xs], Y, [X|Zs]):-efface(Xs, Y, Zs).

/* member(X, Ys) is true if the element X is contained in the list Ys.       */
% member(X, [X|_]).
% member(X, [_|Ys]):-member(X, Ys).

LPA Index     Home Page

Valid HTML 4.01 Strict