OKlibrary  0.2.1.6
BasicNotions.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 30.12.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 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/CombinatorialMatrices/Lisp/Basics.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/CyclicGroups.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/BasicNotions.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Quasigroups/Basics.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Associativity.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00029 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/LatinSquares/BasicNotions.mac")$
00030 
00031 
00032 kill(f)$
00033 
00034 /* *****************************
00035    * Notions of "latin squares *
00036    *****************************
00037 */
00038 
00039 okltest_comlso_p(f) := (
00040   /* XXX */
00041   true)$
00042 
00043 /* Remark: The semantics of okltest_comls_p is identical with that of
00044    okltest_qgrp_p. Currently all tests are handled by okltest_comls_p.
00045 */
00046 okltest_comls_p(f) := (
00047   assert(f(0) = false),
00048   assert(f([]) = false),
00049   assert(f([[],[]]) = false),
00050   assert(f([{},0]) = true),
00051   assert(f([{1},0]) = false),
00052   assert(f(scom_l([1])) = true),
00053   assert(f(scom_l([2])) = false),
00054   assert(f(scom_l([1,2],[2,1])) = true),
00055   assert(f(scom_l([2,1],[1,2])) = true),
00056   assert(f(scom_l([1,2],[2,2])) = false),
00057   for n : 1 thru 6 do
00058     assert(f(qgrp2comls(ugrp2grp(cyclic_ugrp(n)))) = true),
00059   true)$
00060 
00061 okltest_ls_p(f) := (
00062   /* XXX */
00063   true)$
00064 
00065 okltest_hrls_p(f) := (
00066   /* XXX */
00067   assert(f(matrix([2,1],[1,2])) = false),
00068   assert(f(matrix([1,2],[2,1])) = true),
00069   assert(f(matrix([1,3,2],[2,1,3],[3,2,1])) = true),
00070   true)$
00071 
00072 okltest_rls_p(f) := (
00073   /* XXX */
00074   assert(f(matrix([2,1],[1,2])) = false),
00075   assert(f(matrix([1,2],[2,1])) = true),
00076   assert(f(matrix([1,2,3],[3,1,2],[2,3,1])) = false),
00077   assert(f(matrix([1,2,3],[2,3,1],[3,1,2])) = true),
00078   assert(f(matrix([1,3,2],[2,1,3],[3,2,1])) = false),
00079   for n : 1 thru 6 do
00080     assert(f(uqgrp2rls(cyclic_ugrp(n))) = true),
00081   true)$
00082 
00083 
00084 /* *********************
00085    * Various diagonals *
00086    *********************
00087 */
00088 
00089 okltest_main_diagonal(f) := (
00090   assert(f(0) = []),
00091   assert(f(1) = [[1,1]]),
00092   assert(f(2) = [[1,1],[2,2]]),
00093   true)$
00094 
00095 okltest_side_diagonal(f) := (
00096   assert(f(0) = []),
00097   assert(f(1) = [[1,1]]),
00098   assert(f(2) = [[1,2],[2,1]]),
00099   assert(f(3) = [[1,3],[2,2],[3,1]]),
00100   true)$
00101 
00102 okltest_main_pandiagonal(f) := (
00103   for n : 1 thru 6 do
00104     assert(f(n,0) = main_diagonal(n)),
00105   assert(f(2,1) = [[2,1],[1,2]]),
00106   assert(f(3,1) = [[2,1],[3,2],[1,3]]),
00107   assert(f(3,2) = [[3,1],[1,2],[2,3]]),
00108   assert(f(4,1) = [[2,1],[3,2],[4,3],[1,4]]),
00109   assert(f(4,2) = [[3,1],[4,2],[1,3],[2,4]]),
00110   assert(f(4,3) = [[4,1],[1,2],[2,3],[3,4]]),
00111   true)$
00112 
00113 okltest_side_pandiagonal(f) := (
00114   for n : 1 thru 6 do
00115     assert(f(n,n-1) = side_diagonal(n)),
00116   assert(f(2,0) = [[1,1],[2,2]]),
00117   assert(f(3,1) = [[1,2],[2,1],[3,3]]),
00118   assert(f(3,0) = [[1,1],[2,3],[3,2]]),
00119   assert(f(4,2) = [[1,3],[2,2],[3,1],[4,4]]),
00120   assert(f(4,1) = [[1,2],[2,1],[3,4],[4,3]]),
00121   assert(f(4,0) = [[1,1],[2,4],[3,3],[4,2]]),
00122   true)$
00123 
00124 okltest_dls_p(f) := block([a,b,c,d],
00125   assert(f(matrix()) = true),
00126   assert(f(matrix([1])) = true),
00127   assert(f(matrix([1,2],[2,1])) = false),
00128   assert(f(matrix([1,3,2],[a,2,b],[c,d,3])) = false),
00129   assert(f(spdl_abn_ls(5,2,1)) = true),
00130   assert(f(spdl_abn_ls(7,2,1)) = true),
00131   assert(f(cyc3_rls) = false),
00132   assert(f(cyc3_o_hrls) = false),
00133   assert(f(nassoc_rls) = false),
00134   assert(f(dk10_rls) = false),
00135   assert(f(dk10_o_hrls) = false),
00136   assert(f(psssodls_8_ls) = true),
00137   true)$
00138 
00139 okltest_spls_p(f) := block([a,b,c,d],
00140   assert(f(matrix()) = true),
00141   assert(f(matrix([1])) = true),
00142   assert(f(matrix([1,2],[2,1])) = false),
00143   assert(f(matrix([1,3,2],[a,2,b],[c,d,3])) = false),
00144   assert(f(spdl_abn_ls(5,2,1)) = true),
00145   assert(f(spdl_abn_ls(7,2,1)) = true),
00146   assert(f(cyc3_rls) = false),
00147   assert(f(cyc3_o_hrls) = false),
00148   assert(f(nassoc_rls) = false),
00149   assert(f(dk10_rls) = false),
00150   assert(f(dk10_o_hrls) = false),
00151   assert(f(psssodls_8_ls) = false),
00152   true)$
00153 
00154 okltest_pls_p(f) := block([a,b,c,d],
00155   assert(f(matrix()) = true),
00156   assert(f(matrix([1])) = true),
00157   assert(f(matrix([1,2],[2,1])) = false),
00158   assert(f(matrix([1,3,2],[a,2,b],[c,d,3])) = false),
00159   assert(f(spdl_abn_ls(5,2,1)) = true),
00160   assert(f(spdl_abn_ls(7,2,1)) = true),
00161   assert(f(cyc3_rls) = false),
00162   assert(f(cyc3_o_hrls) = false),
00163   assert(f(nassoc_rls) = false),
00164   assert(f(dk10_rls) = false),
00165   assert(f(dk10_o_hrls) = false),
00166   assert(f(psssodls_8_ls) = true),
00167   true)$
00168 
00169 
00170 /* *****************
00171    * Orthogonality *
00172    *****************
00173 */
00174 
00175 okltest_ocomls_p(f) := (
00176   assert(f(scom_l([1]),scom_l([1])) = true),
00177   assert(f(scom_l([1,2],[2,1]), scom_l([1,2],[2,1])) = false),
00178   assert(f(scom_l([1,2],[2,1]), scom_l([2,1],[1,2])) = false),
00179   assert(okltest_ols_p(buildq([f], lambda([A,B], f(m2scom(A),m2scom(B))))) = true),
00180   true)$
00181 
00182 okltest_ols_p(f) := (
00183   /* XXX */
00184   assert(f(cyc3_rls, cyc3_o_hrls) = true),
00185   assert(f(dk10_rls,dk10_o_hrls) = true),
00186   true)$
00187 
00188 okltest_mocomls_p(f) := (
00189   assert(okltest_ocomls_p(buildq([f],lambda([A,B], f([A,B])))) = true),
00190   assert(okltest_mols_p(buildq([f], lambda([L], f(map(m2scom,L))))) = true),
00191   /* XXX */
00192   true)$
00193 
00194 okltest_mols_p(f) := (
00195   assert(okltest_ols_p((buildq([f],lambda([A,B], f([A,B]))))) = true),
00196   /* XXX */
00197   true)$
00198 
00199 okltest_socomls_p(f) := (
00200   assert(okltest_sols_p(buildq([f], lambda([A], f(m2scom(A))))) = true),
00201   /* XXX */
00202   true)$
00203 
00204 okltest_sols_p(f) := (
00205   assert(f(psssodls_8_ls) = true),
00206   /* XXX */
00207   true)$
00208 
00209 
00210 /* ************
00211    * Symmetry *
00212    ************
00213 */
00214 
00215 okltest_ssls_p(f) := (
00216   assert(f(matrix()) = true),
00217   assert(f(matrix([1])) = true),
00218   assert(f(matrix([1,2],[2,1])) = false),
00219   /* XXX */
00220   assert(f(psssodls_8_ls) = true),
00221   true)$
00222 
00223 
00224 /* ***************************
00225    * Sudoku-like constraints *
00226    ***************************
00227 */
00228 
00229 okltest_sdkbox_p(f) := block([x],
00230   assert(f(matrix()) = true),
00231   assert(f(matrix([x])) = true),
00232   assert(f(matrix([1,2],[2,1])) = false),
00233   assert(f(matrix([1,2,1,2],[3,4,3,4],[1,2,1,2],[3,4,3,4])) = true),
00234   /* XXX */
00235   true)$
00236 
00237 
00238 /* ****************
00239    * Combinations *
00240    ****************
00241 */
00242 
00243 okltest_sdk_p(f) := (
00244   assert(f(0) = false),
00245   assert(f(matrix()) = true),
00246   assert(f(matrix([])) = false),
00247   assert(f(matrix([0])) = false),
00248   assert(f(matrix([1])) = true),
00249   assert(f(matrix([1,2],[2,1])) = false),
00250   /* XXX */
00251   true)$
00252 
00253 okltest_sodls_p(f) := block([x],
00254   assert(f(0) = false),
00255   assert(f(matrix()) = true),
00256   assert(f(matrix([x])) = false),
00257   assert(f(matrix([1])) = true),
00258   assert(f(psssodls_8_ls) = true),
00259   assert(f(psssodls_9_ls) = true),
00260   /* XXX */
00261   true)$
00262 
00263 okltest_sssodls_p(f) := (
00264   assert(f(sssodls_4_ls) = true),
00265   assert(f(psssodls_8_ls) = true),
00266   assert(f(psssodls_9_ls) = true),
00267   /* XXX */
00268   true)$
00269 
00270 okltest_psssodls_p(f) := (
00271   assert(f(psssodls_8_ls) = true),
00272   assert(f(psssodls_9_ls) = true),
00273   assert(f(psssodls_20_ls) = true),
00274   /* XXX */
00275   true)$
00276 
00277 
00278 /* ************
00279    * Examples *
00280    ************
00281 */
00282 
00283 okltest_cyc3_rls(f) := (
00284   assert(matrix_size(f) = [3,3]),
00285   assert(rls_p(f) = true),
00286   true)$
00287 
00288 okltest_cyc3_o_hrls(f) := block([Q],
00289   assert(matrix_size(f) = [3,3]),
00290   assert(rls_p(f) = false),
00291   assert(hrls_p(f) = true),
00292   assert(ocomls_p(m2scom(f),m2scom(cyc3_rls)) = true),
00293   Q : ls2qgrp(f),
00294   assert(qgrp_p(Q) = true),
00295   assert(has_neutral_el_grd(Q) = false),
00296   assert(associative_bydef_grd(Q) = false),
00297   true)$
00298 
00299 okltest_nassoc_rls(f) := block([Q],
00300   assert(matrix_size(f) = [5,5]),
00301   assert(rls_p(f) = true),
00302   Q : rls2uqgrp(f),
00303   assert(uqgrp_p(Q) = true),
00304   assert(associative_bydef_grd(ugrd2grd(Q)) = false),
00305   true)$
00306 
00307 okltest_dk10_rls(f) := (
00308   assert(matrix_size(f) = [10,10]),
00309   assert(rls_p(f) = true),
00310   true)$
00311 
00312 okltest_dk10_o_hrls(f) := (
00313   assert(matrix_size(f) = [10,10]),
00314   assert(rls_p(f) = false),
00315   assert(hrls_p(f) = true),
00316   assert(ocomls_p(m2scom(f),m2scom(dk10_rls)) = true),
00317   true)$
00318 
00319 okltest_sssodls_4_ls(f) := (
00320   assert(matrix_size(f) = [4,4]),
00321   assert(sssodls_p(f) = true),
00322   assert(pls_p(f) = false),
00323   assert(sdk_p(f) = true),
00324   true)$
00325 
00326 okltest_psssodls_8_ls(f) := (
00327   assert(matrix_size(f) = [8,8]),
00328   assert(psssodls_p(f) = true),
00329   assert(spls_p(f) = false),
00330   true)$
00331 
00332 okltest_psssodls_9_ls(f) := (
00333   assert(matrix_size(f) = [9,9]),
00334   assert(psssodls_p(f) = true),
00335   assert(spls_p(f) = false),
00336   assert(sdk_p(f) = true),
00337   true)$
00338 
00339 okltest_psssodls_20_ls(f) := (
00340   assert(matrix_size(f) = [20,20]),
00341   assert(psssodls_p(f) = true),
00342   assert(spls_p(f) = false),
00343   assert(sdk_p(f) = false),
00344   true)$
00345 
00346 
00347 /* **************
00348    * Generators *
00349    **************
00350 */
00351 
00352 okltest_spdl_abn_ls(f) := (
00353   for n : 3 thru if oklib_test_level=0 then 20 else 40 do
00354     if divide(n,2)[2]#0 and divide(n,3)[2]#0 then block([L:f(n,2,1)],
00355       assert(ls_p(L)),
00356       assert(spls_p(L))
00357   ),
00358   true)$
00359 
00360 okltest_spdl_abn_ls_p(f) := (
00361   for n : 3 thru if oklib_test_level=0 then 20 else 40 do
00362     if divide(n,2)[2]#0 and divide(n,3)[2]#0 then
00363       assert(f(n,2,1) = true),
00364   true)$
00365 
00366 /* ***************
00367    * Conversions *
00368    ***************
00369 */
00370 
00371 okltest_qgrp2comls(f) := (
00372   /* XXX */
00373   true)$
00374 
00375 okltest_uqgrp2rls(f) := (
00376   assert(f([{77},lambda([x,y],77),77]) = matrix([1])),
00377   assert(f(rls2uqgrp(nassoc_rls)) = nassoc_rls),
00378   for n : 1 thru 5 do block(
00379    [M : f(cyclic_ugrp(n)),
00380     L : create_list(i,i,1,n)],
00381     assert(M = apply(matrix, create_list(rotate(L,-i),i,0,n-1)))
00382   ),
00383   /* XXX */
00384   true)$
00385 
00386