OKlibrary  0.2.1.6
Generators.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 29.11.2007 (Swansea) */
00002 /* Copyright 2007, 2008, 2009, 2010, 2011, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/PrimeNumbers.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Combinatorics/Lisp/Enumeration/Subsets.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/VanderWaerden.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/Numerical/Lisp/Norms.mac")$
00029 
00030 
00031 /* ************************
00032    * Complete hypergraphs *
00033    ************************
00034 */
00035 
00036 /* The complete r-graph with vertex set V: */
00037 complete_hg(V,r) := [V, powerset(V,r)]$
00038 /* The standardised complete r-graph: */
00039 complete_stdhg(n,r) := complete_hg(setn(n),r)$
00040 
00041 /* Using colexicographical order, where V now is a list: */
00042 complete_ohg(V,r) := [V, colex_ksubsets_ll(V,r)]$
00043 complete_stdohg(n,r) := complete_ohg(create_list(i,i,1,n),r)$
00044 
00045 /* Statistics functions: */
00046 
00047 nver_complete_hg(n,r) := n$
00048 nhyp_complete_hg(n,r) := binomial(n,r)$
00049 
00050 
00051 /* The "colouring hypergraph" for colour-set V: */
00052 colouring_hg(V) := [V, setdifference(powerset(V), adjoin({},powerset(V,1)))]$
00053 colouring_stdhg(n) := colouring_hg(setn(n))$
00054 
00055 /* Statistics functions: */
00056 
00057 nver_colouring_hg(n) := n$
00058 nhyp_colouring_hg(n) := 2^n-n-1$
00059 
00060 
00061 /* ***************************
00062    * Generalised Tic-tac-toe *
00063    ***************************
00064 */
00065 
00066 /*
00067   Let m >= 1 be the numbers of rows and n >= 1 the number of columns.
00068 */
00069 
00070 /*
00071   Computing the horizontal, vertical and diagonal lines:
00072   - each of the four collection of lines represents a partitioning
00073     of the m*n fields of the rectangle;
00074   - direction of "scanning" is from left to right, and top to bottom.
00075 */
00076 
00077 /* First the representations of the complete lines (of maximal length) by
00078    their two endpoints, via the matrix-indices (1-based).
00079 */
00080 
00081 /* Horizontal lines (slope [0,1]): */
00082 gttt_horiz(m,n) := create_list([[i,1],[i,n]], i,1,m)$
00083 /* Vertical lines (slope [1,0]): */
00084 gttt_vert(m,n) := create_list([[1,i],[m,i]], i,1,n)$
00085 
00086 /* Diagonals from top-left to bottom-right (the "principal diagonal"
00087    and its parallels; slope [1,1]):
00088 */
00089 gttt_tlbr(m,n) := create_list(
00090  [[max(m-i+1,1),max(i-m+1,1)],[m-max(i-n,0), min(i,n)]],
00091  i,1,m+n-1)$
00092 
00093 /* Diagonals from bottom-left to top-right (the "antidiagonal" and its
00094    parallels; slope [1,-1]):
00095 */
00096 gttt_bltr(m,n) :=
00097  map(lambda([L], map(lambda([p],[m-p[1]+1,p[2]]), L)),
00098      gttt_tlbr(m,n))$
00099 
00100 /*
00101   All maximal lines, in the order horizontal, vertical, top-left to
00102   bottom-right, bottom-left to top-right, with repetition (only the first
00103   occurrence of a line remains), represented by the two end-points:
00104 */
00105 gttt_lines(m,n) :=
00106  if m=1 and n=1 then [[[1,1],[1,1]]]
00107  else if m=1 or n=1 then append(gttt_horiz(m,n), gttt_vert(m,n))
00108  else append(gttt_horiz(m,n), gttt_vert(m,n), gttt_tlbr(m,n), gttt_bltr(m,n))$
00109 
00110 /* A line as a sequence of points, of length k with start-point p and
00111    slope [dx,dy], is created by
00112      arpr(k,p,[dx,dy]).
00113    The possible [dx,dy] here are (given that we standardise movement by only
00114    going from left to right or top to bottom):
00115    - [0,1] (horizontal),
00116    - [1,0] (vertical),
00117    - [1,1] (top-left to bottom-right),
00118    - [-1,1] (bottom-left to top-right).
00119    Trivial lines (length 1) shall have slope [0,0].
00120 */
00121 
00122 /* The length of a line (as the number of vertices in it) given by the two
00123    endpoints:
00124 */
00125 gttt_length(a,b) := dist_vec(a,b,inf)+1$
00126 
00127 /* For two endpoints a,b the slope [dx,dy]: */
00128 gttt_slope(a,b) := [signum(first(b)-first(a)), signum(second(b)-second(a))]$
00129 
00130 /* For a line represented by two endpoints a,b, the list of the pairs
00131    [start-point, slope] for lines of length at least k >= 1:
00132 */
00133 gttt_startpoints(a,b,k) := block([l : gttt_length(a,b), s : gttt_slope(a,b)],
00134  create_list([a+i*s,s], i,0,l-k))$
00135 
00136 /* All (different) lines of length (exactly) k >= 1, represented by pairs
00137    [start-point, slope]:
00138 */
00139 gttt_lines_k(k,m,n) :=
00140  if k=1 then create_list([[i,j],[0,0]], i,1,m, j,1,n)
00141  else lappend(
00142    map(lambda([p], gttt_startpoints(p[1],p[2],k)),
00143        sublist(gttt_lines(m,n), lambda([p], apply(gttt_length,p)>=k))))$
00144 
00145 /* The ordered hypergraph underlying generalised tic-tac-toe (k in a row
00146    on an mxn board), with vertices the pairs [i,j] and hyperedges the lines
00147    (horizontal, vertical, diagonal, anti-diagonal) of length k:
00148 */
00149 gttt_ohg(k,m,n) := [
00150  create_list([i,j], i,1,m, j,1,n),
00151  map(setify, map(lambda([p], arpr(k, p[1], p[2])), gttt_lines_k(k,m,n)))
00152 ]$
00153 
00154