Projective Planes and Difference Sets

This is based on a description given in "An Introduction to Combinatorial Designs" by D. R. Stinson.

/* bibd(N, BIBD) is true if BIBD is an order N projective plane, that is,    */
/*   a (N^2+N+1, N+1, 1)-BIBD, that is, a c(N^2+N+1, N+1, 2, 2, N^2+N+1).    */
/*   cover. On backtracking, other solutions will be found.                  */
/* e.g. bibd(2, [[1,2,4],[1,3,7],[1,5,6],[2,3,5],[2,6,7],[3,4,6],[4,5,7]]).  */
bibd(N, BIBD):-
  difference_set(N, Set),
  V is N*N + N + 1,
  bibd_1(V, V, Set, BIBD0),
  sort(BIBD0, BIBD).

bibd_1(0, _, _, []):-!.
bibd_1(I, V, Set, [Block|BIBD]):-
  I1 is I - 1,
  bibd_2(Set, I1, V, [], Block),
  bibd_1(I1, V, Set, BIBD).

bibd_2([], _, _, Block, Block).
bibd_2([X|Set], Y, V, Block0, Block):-
  Point is (X + Y) mod V + 1,
  insert(Block0, Point, Block1),
  bibd_2(Set, Y, V, Block1, Block).

/* difference_set(N, Set) is true if Set is a (N^2+N+1, N+1, 1)-difference   */
/*   set, that is, N+1 numbers di from 0..N^2+N such that each of the        */
/*   numbers 1..N^2+N appears once in the set {(di-dj) mod (N^2+N+1)}. On    */
/*   backtracking, all solutions will be found.                              */
/* e.g. difference_set(5, [0,1,3,8,12,18]).                                  */
difference_set(N, Set):-
  V is N*N + N + 1,
  V1 is V - 1,
  integers(0, V1, Gs),
  K is N + 1,
  difference_set_1(K, Gs, V, [], [], Set0),
  reverse(Set0, Set).

difference_set_1(0, _, _, _, Set, Set):-!.
difference_set_1(I, Gs, V, Hs, Set0, Set):-
  rest(G, Gs, Gs1),
  difference_set_2(Set0, G, V, Hs, Hs1),
  I1 is I - 1,
  difference_set_1(I1, Gs1, V, Hs1, [G|Set0], Set).

difference_set_2([], _, _, Hs, Hs).
difference_set_2([X|Set], Y, V, Hs0, Hs):-
  A is Y - X, /* (Y - X) mod V */
  B is V - A, /* (X - Y) mod V */
  minimum(A, B, C),
  \+ member(C, Hs0),  
  difference_set_2(Set, Y, V, [C|Hs0], Hs).

/* insert(Ys, X, Zs) is true if Zs is the result of inserting X into the     */
/*   ordered list Ys.                                                        */
insert([Y|Ys], X, [Y|Zs]):-Y < X, !, insert(Ys, X, Zs).
insert(Ys, X, [X|Ys]).

/* integers(M, N, Is) is true if Is is the list of integers from M to N      */
/*   inclusive.                                                              */
integers(N, N, [N]):-!.
integers(I, N, [I|Is]):-I < N, I1 is I + 1, integers(I1, N, Is).

/* member(X, Xs) is true if the element X is contained in the list Xs. On    */
/*   backtracking, all solutions will be found.                              */
%member(X, [X|_]).
%member(X, [_|Xs]):-member(X, Xs).

/* minimum(X, Y, Z) is true if Z is the minimum of the numbers X and Y.      */
minimum(X, Y, Z):-X =< Y, !, Z = X.
minimum(_, Y, Y).

/* rest(X, Ys, Zs) is true if X is a member of the list Ys, and the list Zs  */
/*   is the rest of the list following X. On backtracking, all solutions     */
/*   will be found.                                                          */
rest(X, [X|Ys], Ys).
rest(X, [_|Ys], Zs):-rest(X, Ys, Zs).

/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of the */
/*   elements in the list Xs.                                                */
%reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

%reverse_1([], As, As).
%reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

LPA Index     Home Page

Valid HTML 4.01 Strict