OKlibrary  0.2.1.6
Gasarch.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 26.10.2009 (Swansea) */
00002 /* Copyright 2009, 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/DataStructures/Lisp/Lists.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00025 
00026 
00027 /* *****************************************************
00028    * Hypergraphs of sub-square-vertices in a rectangle *
00029    *****************************************************
00030 */
00031 
00032 /* Variables sqv(i,j) for field (i,j): */
00033 kill(sqv)$
00034 declare(sqv,noun)$
00035 sqv_var(i,j) := nounify(sqv)(i,j)$
00036 sqv_pair(P) := nounify(sqv)(first(P),second(P))$
00037 
00038 /* Enumerating the fields of a p x q rectangle in layers, starting left-top,
00039    using matrix-indices, where each layer k is a vertical line from top to
00040    bottom followed by a horizontal line from right to left (the first layer
00041    has height and width 1, length 1, the second height and width 2, length 3,
00042    the third height and width 3, length 5, and so on (assuming p=q here);
00043    the fields [i,j] on layer k are characterised by max(i,j) = k):
00044 */
00045 enumerate_rectangle(p,q) := block([m : min(p,q), R],
00046  R : lappend(create_list(append(create_list([j,i], j,1,i), create_list([i,i-j], j,1,i-1)), i,1,m)),
00047  R : append(R, lappend(create_list(create_list([i,m-j], j,0,m-1), i,m+1,p))),
00048  R : append(R, lappend(create_list(create_list([j,i], j,1,m), i,m+1,q))),
00049  R)$
00050 
00051 /* The ordered hypergraph with vertex set the fields of a p x q rectangle,
00052    ordered according to enumerate_rectangle(p,q), and with hyperedges all
00053    subsets with (exactly) 4 vertices which are the corners of some rectangle;
00054    p, q are natural numbers >= 0:
00055 */
00056 gasarch_ohg(p,q) := [
00057  map(sqv_pair,enumerate_rectangle(p,q)),
00058  map(lambda([p], map(sqv_pair, cartesian_product(first(p),second(p)))), cartesian_product_l(map(listify,[powerset(setn(p),2), powerset(setn(q),2)])))]$
00059 gasarch_hg(p,q) := ohg2hg(gasarch_ohg(p,q))$
00060 
00061 /* Computing standardisation functions, which standardise the variables
00062    sqv(i,j) from a p x q rectangle according to the order given by
00063    enumerate_rectangle:
00064 */
00065 standardise_gasarch(p,q) :=
00066   buildq([p,q], lambda([t],
00067    ev(t,
00068       sqv(i,j):=(min(max(i,j)-1,p)+1)*min(max(i,j)-1,q)+1-j +
00069                 if i>q then 0 else i,
00070       sqv)))$
00071 /* Computing the inversion function (which just applies to natural
00072    numbers, not to terms like the standardisation-function): */
00073 invstandardise_gasarch(p,q) :=
00074   buildq([q], lambda([i], unknown))$
00075 
00076 /* The hypergraph isomorphic to gasarch_ohg(p,q), standardised according
00077    to the given order:
00078 */
00079 gasarch_stdohg(p,q) := block([s : standardise_gasarch(p,q)],
00080  s(gasarch_ohg(p,q)))$
00081 gasarch_stdhg(p,q) := ohg2hg(gasarch_stdohg(p,q))$
00082 
00083 
00084 /* **************
00085    * Statistics *
00086    **************
00087 */
00088 
00089 nver_gasarch_ohg(p,q) := p*q$
00090 nver_gasarch_hg(p,q) := nver_gasarch_ohg(p,q)$
00091 
00092 nhyp_gasarch_ohg(p,q) := if p<=1 or q <=1 then 0
00093  else (binomial(p*q,2) - p*binomial(q,2) - q*binomial(p,2))/2$
00094 nhyp_gasarch_hg(p,q) := nhyp_gasarch_ohg(p,q)$
00095