Transversal Designs

Constructs a transversal design TD(k,n) from k-2 mutually orthogonal Latin squares (MOLS) of order n. Many MOLS can be constructed using the Mutually Orthogonal Latin Squares package.

/*
 * A transversal design TD(k,n) with k>1 and n>0 is a triple (X,G,B) such that:
 * 1. X is a set of kn elements called points
 * 2. G is a partition of X into k subsets of size n called groups
 * 3. B is a set of k-subsets of X called blocks
 * 4. any group and any block contain exactly one common point, and
 * 5. every pair of points from distinct groups is contained in exactly one
 *    block
 */

% Constructs the Groups and Blocks of a Transversal Design TD(k,n) from k-2
%   of the specified MOLS of order n.
% e.g. mols_td([[1,2,3,3,1,2,2,3,1], [1,2,3,2,3,1,3,1,2]], 3, 3, G, B) gives
%   G=[[1,2,3],[4,5,6],[7,8,9]]
%   B=[[1,4,7],[1,5,8],[1,6,9],[2,4,9],[2,5,7],[2,6,8],[3,4,8],[3,5,9],[3,6,7]]
% e.g. mols_td([[1,2,3,3,1,2,2,3,1], [1,2,3,2,3,1,3,1,2]], 4, 3, G, B) gives
%   G=[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
%   B=[[1,4,7,10],[1,5,8,11],[1,6,9,12],[2,4,9,11],[2,5,7,12],
%      [2,6,8,10],[3,4,8,12],[3,5,9,10],[3,6,7,11]]
mols_td(MOLS, K, N, Groups, Blocks):-
  T is K - 2,
  mols_oa(MOLS, T, N, OA),
  oa_td(OA, Groups, Blocks).

% Constructs the Orthogonal Array OA(t+2,n) from t of the specified MOLS
%   of order n.
% e.g. mols_oa([[1,2,3,3,1,2,2,3,1], [1,2,3,2,3,1,3,1,2]], 1, 3, OA) gives
%   OA=[[1,1,1],[1,2,2],[1,3,3],[2,1,3],[2,2,1],[2,3,2],[3,1,2],[3,2,3],[3,3,1]]
% e.g. mols_oa([[1,2,3,3,1,2,2,3,1], [1,2,3,2,3,1,3,1,2]], 2, 3, OA) gives
%   OA=[[1,1,1,1],[1,2,2,2],[1,3,3,3],[2,1,3,2],[2,2,1,3],
%       [2,3,2,1],[3,1,2,3],[3,2,3,1],[3,3,1,2]]
mols_oa(MOLS, T, N, OA):-
  T < N,
  first_n(T, MOLS, MOLS1),
  mols_oa_1(MOLS1, 1, 1, N, OA).

mols_oa_1([], _, _, _, []):-!.
mols_oa_1(MOLS, I, J, N, [[I,J|Row]|OA]):-
  heads_and_tails(MOLS, Row, MOLS1),
  next(I, J, N, I1, J1),
  mols_oa_1(MOLS1, I1, J1, N, OA).

% Selects the first N elements of Xss
first_n(0, _, []):-!.
first_n(I, [Xs|Xss], [Xs|Yss]):-
  I1 is I - 1,
  first_n(I1, Xss, Yss).

next(I, J, N, I, J1):-
  J < N, !,
  J1 is J + 1.
next(I, N, N, I1, 1):-
  I1 is I + 1.

/* heads_and_tails(ListOfLists, Heads, Tails) is true if Heads is the list   */
/*   of the heads of the members of the ListOfLists, and Tails is the list   */
/*   of the (non-empty) tails of the members of the ListOfLists.             */
/*   e.g. heads_and_tails([[1,2,3],[4,5,6]], [1,4], [[2,3],[5,6]]).          */
/*   e.g. heads_and_tails([[1,2,3],[4]],     [1,4], [[2,3]]).                */
heads_and_tails([], [], []).
heads_and_tails([[X]|Xss], [X|Ys], Zss):-!,
  heads_and_tails(Xss, Ys, Zss).
heads_and_tails([[X,X1|Xs]|Xss], [X|Ys], [[X1|Xs]|Zss]):-
  heads_and_tails(Xss, Ys, Zss).

% Constructs the Transversal Design TD(k,n) from an Orthogonal Array OA(k,n)
% e.g. oa_td([[1,1,1],[1,2,2],[2,1,2],[2,2,1]], G, B) gives
%   G=[[1,2],[3,4],[5,6]]
%   B=[[1,3,5],[1,4,6],[2,3,6],[2,4,5]]
oa_td(OA, Groups, Blocks):-
  length(OA, N2),
  N is sqrt(N2),
  OA=[Row|_],
  length(Row, K),
  K_1 is K - 1,
  findall(Group, group(K_1, N, Group), Groups),
  blocks(OA, N, Blocks).

group(K1, N, Group):-
  do(0, K1, J),
  findall(GroupElement, group_1(N, J, GroupElement), Group).

group_1(N, J, X):-
  do(1, N, I),
  X is N * J + I.

% There is one block for each row of the OA
blocks([], _, []).
blocks([Row|OA], N, [Block|Blocks]):-
  blocks_1(Row, 0, N, Block),
  blocks(OA, N, Blocks).

blocks_1([], _, _, []).
blocks_1([I|Row], J, N, [K|Block]):-
  K is N * J + I,
  J1 is J + 1,
  blocks_1(Row, J1, N, Block).

/* do(I, J, K) is true if K is an integer between I and J inclusive.         */
do(I, J, I):-I =< J.
do(I, J, K):-I < J, I1 is I + 1, do(I1, J, K).

LPA Index     Home Page

Valid HTML 4.0!