OKlibrary  0.2.1.6
VanderWaerden.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 23.10.2010 (Swansea) */
00002 /* Copyright 2010, 2011 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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/VanderWaerden.mac")$
00026 
00027 kill(f)$
00028 
00029 
00030 /* ***************************
00031    * Arithmetic progressions *
00032    ***************************
00033 */
00034 
00035 okltest_arpr(f) := block([a,d],
00036   assert(f(0,a,d) = []),
00037   assert(f(1,a,d) = [a]),
00038   assert(f(2,a,d) = [a,a+d]),
00039   assert(f(3,a,d) = [a,a+d,a+2*d]),
00040   assert(f(4,a,d) = [a,a+d,a+2*d,a+3*d]),
00041   assert(f(2,a,-1) = [a,a-1]),
00042   true)$
00043 
00044 okltest_arithmetic_progression_p(f) := (
00045   assert(f([]) = true),
00046   assert(f([1]) = true),
00047   assert(f([1,3]) = true),
00048   assert(f([1,2,3]) = true),
00049   assert(f([1,2,4]) = false),
00050   assert(f([1,3,5,7]) = true),
00051   assert(f([1,3,4,6]) = false),
00052   true)$
00053 
00054 okltest_arithmetic_progression_d_p(f) := block([x,y],
00055   assert(f([],x) = true),
00056   assert(f([x],y) = true),
00057   assert(f([x,y],y-x) = true),
00058   assert(f([x,x,x],0) = true),
00059   assert(f([x,y],0) = false),
00060   assert(f([1,2,3,4],1) = true),
00061   assert(f([1,2,3,4,6],1) = false),
00062   for k : 0 thru 4 do
00063     assert(f(arpr(k,x,y),y) = true),
00064   true)$
00065 
00066 
00067 /* ***************************************************
00068    * Standard hypergraphs of arithmetic progressions *
00069    ***************************************************
00070 */
00071 
00072 okltest_arithprog_finish(f) := (
00073   assert(f(1,1) = [{1}]),
00074   assert(f(1,2) = [{2}]),
00075   assert(f(2,1) = []),
00076   assert(f(2,2) = [{1,2}]),
00077   assert(f(2,3) = [{1,3},{2,3}]).
00078   assert(f(3,1) = []),
00079   assert(f(3,2) = []),
00080   assert(f(3,3) = [{1,2,3}]),
00081   assert(f(3,4) = [{2,3,4}]),
00082   assert(f(3,5) = [{1,3,5},{3,4,5}]),
00083   assert(f(3,6) = [{2,4,6},{4,5,6}]),
00084   true)$
00085 
00086 okltest_arithprog_ohg(f) := (
00087   assert(f(0,0) = [[],[{}]]),
00088   assert(f(0,1) = [[1],[{}]]),
00089   assert(f(1,0) = [[],[]]),
00090   assert(f(1,1) = [[1],[{1}]]),
00091   assert(f(1,2) = [[1,2],[{1},{2}]]),
00092   assert(f(2,0) = [[],[]]),
00093   assert(f(2,1) = [[1],[]]),
00094   assert(f(2,2) = [[1,2],[{1,2}]]),
00095   assert(f(2,3) = [[1,2,3],[{1,2},{1,3},{2,3}]]),
00096   assert(f(3,0) = [[],[]]),
00097   assert(f(3,1) = [[1],[]]),
00098   assert(f(3,2) = [[1,2],[]]),
00099   assert(f(3,3) = [[1,2,3],[{1,2,3}]]),
00100   assert(f(3,4) = [[1,2,3,4],[{1,2,3},{2,3,4}]]),
00101   assert(f(3,5) = [[1,2,3,4,5],[{1,2,3},{2,3,4},{1,3,5},{3,4,5}]]),
00102   for k : 0 thru 4 do
00103     for n : 0 thru 4 do
00104       assert(ohg_p(f(k,n))),
00105   assert(okltest_arithprog_hg(buildq([f],lambda([k,n],ohg2hg(f(k,n)))))),
00106   true)$
00107 
00108 okltest_arithprog_hg(f) := (
00109   assert(f(0,0) = [{},{{}}]),
00110   assert(f(1,0) = [{},{}]),
00111   assert(f(0,1) = [{1},{{}}]),
00112   assert(f(1,1) = [{1},{{1}}]),
00113   assert(f(2,1) = [{1},{}]),
00114   for n : 0 thru 4 do block([N : setn(n)],
00115     for k in [0,1,2,n] do
00116       assert(f(k,n) = [N,powerset(N,k)])
00117   ),
00118   assert(f(3,4) = [{1,2,3,4},{{1,2,3},{2,3,4}}]),
00119   true)$
00120 
00121 okltest_nver_arithprog_hg(f) := (
00122   for k : 0 thru 4 do
00123     for n : 0 thru 5 do
00124       assert(f(k,n) = length(arithprog_hg(k,n)[1])),
00125   true)$
00126 
00127 okltest_nver_arithprog_ohg(f) := (
00128   for k : 0 thru 4 do
00129     for n : 0 thru 5 do
00130       assert(f(k,n) = length(arithprog_ohg(k,n)[1])),
00131   true)$
00132 
00133 okltest_nhyp_arithprog_hg(f) := (
00134   for k : 0 thru if oklib_test_level=0 then 4 else 6 do
00135     for n : 0 thru if oklib_test_level=0 then 6 else 10 do
00136       assert(f(k,n) = length(arithprog_hg(k,n)[2])),
00137   true)$
00138 
00139 okltest_nhyp_arithprog_ohg(f) := (
00140   for k : 0 thru if oklib_test_level=0 then 4 else 6 do
00141     for n : 0 thru if oklib_test_level=0 then 6 else 10 do
00142       assert(f(k,n) = length(arithprog_ohg(k,n)[2])),
00143   true)$
00144 
00145 
00146 /* ******************************************************
00147    * Generalised hypergraphs of arithmetic progressions *
00148    ******************************************************
00149 */
00150 
00151 okltest_arithmetic_progressions(f) := block([x,y,z],
00152   assert(f([],0) = [[]]),
00153   assert(f([1],0) = [[]]),
00154   assert(f([],1) = []),
00155   assert(f([1],1) = [[1]]),
00156   assert(f([2,4],1) = [[2],[4]]),
00157   assert(f([],2) = []),
00158   assert(f([1],2) = []),
00159   assert(f([1,3],2) = [[1,3]]),
00160   assert(f([1,2,3],2) = [[1,2],[1,3],[2,3]]),
00161   assert(f([1,3,4,6],2) = [[1,3],[1,4],[1,6],[3,4],[3,6],[4,6]]),
00162   assert(f([1,2,3],3) = [[1,2,3]]),
00163   assert(f([1,3,4,6],3) = []),
00164   assert(f([1,3,4,5,6],3) = [[1,3,5],[3,4,5],[4,5,6]]),
00165   assert(f([1,3,5,6,8,9,10,12],3) = [[1,3,5],[1,5,9],[3,6,9],[6,8,10],[6,9,12],[8,9,10],[8,10,12]]),
00166   assert(okltest_arithprog_hg(buildq([f],lambda([k,n],ohg2hg([create_list(i,i,1,n),map(setify,f(create_list(i,i,1,n),k))]))))),
00167   assert(f([x,y,z],2) = [[x,y],[x,z],[y,z]]),
00168   true)$
00169 
00170 okltest_arithprog_list_ohg(f) := (
00171   assert(f(3,[1,2,3,4,5]) = [[1,2,3,4,5], [{1,2,3},{1,3,5},{2,3,4},{3,4,5}]]),
00172   assert(f(3,[3,5,8]) = [[3,5,8],[]]),
00173   true)$
00174 
00175 okltest_arithprog_list_hg(f) := (
00176   assert(okltest_arithprog_hg(buildq([f], lambda([k,n], f(k,create_list(i,i,1,n))))) = true).
00177   assert(f(3,[3,5,8]) = [{3,5,8},{}]),
00178   true)$
00179 
00180 okltest_has_arithprog(f) := block([S,x],
00181   assert(f(S,-1) = false),
00182   assert(f(S,0) = true),
00183   assert(f({x},1) = true),
00184   assert(f({-1,5},2) = true),
00185   assert(f({1,3,5},3) = true),
00186   assert(f({1,3,6},3) = false),
00187   true)$
00188 
00189 
00190 /* ************
00191    * Symmetry *
00192    ************
00193 */
00194 
00195 okltest_mirrorfold_vdw(f) := block([m],
00196   m : f(0),
00197   m : f(1),
00198   assert(m(1) = 1),
00199   m : f(2),
00200   assert(m(1) = 1),
00201   assert(m(2) = 1),
00202   m : f(3),
00203   assert(m(1) = 1),
00204   assert(m(2) = 2),
00205   assert(m(3) = 1),
00206   m : f(4),
00207   assert(create_list(m(i),i,1,4) = [1,2,2,1]),
00208   assert(create_list(f(5)(i),i,1,5) = [1,2,3,2,1]),
00209   assert(create_list(f(6)(i),i,1,6) = [1,2,3,3,2,1]),
00210   true)$
00211 
00212 okltest_palindromise_vdw_ohg(f) := block([x],
00213   assert(f([[],[x]]) = [[],[x]]),
00214   assert(f([[1],[]]) = [[1],[]]),
00215   assert(f([[1],[{}]]) = [[1],[{}]]),
00216   assert(f([[1],[{1}]]) = [[1],[{1}]]),
00217   assert(f([[1,2],[]]) = [[1],[]]),
00218   assert(f([[1,2],[{1},{1,2},{2}]]) = [[1],[{1}]]),
00219   assert(f([[1,2,3],[{1}]]) = [[1,2],[{1}]]),
00220   assert(f([[1,2,3],[{1},{1,2,3},{2,3}]]) = [[1,2],[{1}]]),
00221   assert(f([[1,2,3,4],[{2,4},{1,3},{2,3},{1,4}]]) = [[1,2],[{1},{2}]]),
00222   assert(f(arithprog_ohg(3,7)) = [[1,2,3,4],[{1,3},{1,4},{2,4},{3,4}]]),
00223   assert(f(arithprog_ohg(3,8)) = [[1,2,3,4],[{1,2,3},{1,2,4},{3,4}]]),
00224   assert(f(arithprog_ohg(3,9)) = [[1,2,3,4,5],[{1,2,3},{2,4},{1,3,4},{1,5},{2,5},{3,5},{4,5}]]),
00225   assert(okltest_palindromise_vdw_hg(buildq([f],lambda([G], ohg2hg(f(hg2ohg(G)))))) = true),
00226   true)$
00227 
00228 okltest_palindromise_vdw_hg(f) := block([x],
00229   assert(f([{},{x}]) = [{},{x}]),
00230   assert(f([{1},{}]) = [{1},{}]),
00231   assert(f([{1},{{}}]) = [{1},{{}}]),
00232   assert(f([{1,2},{}]) = [{1},{}]),
00233   for n : 0 thru 6 do
00234     assert(f(arithprog_hg(2,n)) = block([V:setn(ceiling(n/2))],
00235       [V, if n<=1 then {} else singletons(disjoin((n+1)/2,V))])),
00236   assert(f(arithprog_hg(4,7)) = [{1,2,3,4},{{1,3},{2,3,4}}]),
00237   assert(f(arithprog_hg(4,8)) = [{1,2,3,4},{{3,4}}]),
00238   true)$
00239 
00240 okltest_arithprog_pd_hg(f) := (
00241   for k : 0 thru if oklib_test_level=0 then 7 else 10 do
00242     for n : 0 thru if oklib_test_level=0 then 9 else 20 do (
00243       assert(f(k,n) = palindromise_vdw_hg(arithprog_hg(k,n)))),
00244   true)$
00245 
00246