OKlibrary  0.2.1.6
Schur.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 15.7.2012 (Swansea) */
00002 /* Copyright 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/TestSystem/Lisp/Asserts.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/Schur.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Statistics.mac")\$
00025 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/CyclicGroups.mac")\$
00026
00027 kill(f)\$
00028
00029
00030 /* *******************
00031    * Schur's theorem *
00032    *******************
00033 */
00034
00035 okltest_schurtriples_ohg(f) := (
00036   assert(f(0) = [[],[]]),
00037   assert(f(1) = [[1],[]]),
00038   assert(f(2) = [[1,2], [{1,1,2}]]),
00039   assert(f(3) = [[1,2,3], [{1,2},{1,2,3}]]),
00040   assert(f(4) = [[1,2,3,4], [{1,2},{1,2,3},{1,3,4},{2,2,4}]]),
00041   assert(f(5) = [[1,2,3,4,5],[{1,2},{1,2,3},{1,3,4},{2,2,4},{1,4,5},{2,3,5}]]),
00042   assert(f(6) = [[1,2,3,4,5,6],[{1,2},{1,2,3},{1,3,4},{2,2,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6},{3,6}]]),
00043   true)\$
00044
00045 okltest_schurtriples_hg(f) := (
00046   assert(f(0) = [{},{}]),
00047   assert(f(1) = [{1},{}]),
00048   assert(f(2) = [{1,2}, {{1,1,2}}]),
00049   assert(f(3) = [{1,2,3}, {{1,2},{1,2,3}}]),
00050   assert(f(4) = [{1,2,3,4}, {{1,2},{1,2,3},{1,3,4},{2,2,4}}]),
00051   true)\$
00052
00053 okltest_schurtriples_me_ohg(f) := (
00054   assert(f(0) = [[],[]]),
00055   assert(f(1) = [[1],[]]),
00056   assert(f(2) = [[1,2], [{1,1,2}]]),
00057   assert(f(3) = [[1,2,3], [{1,2}]]),
00058   assert(f(4) = [[1,2,3,4], [{1,2},{1,3,4},{2,2,4}]]),
00059   assert(f(5) = [[1,2,3,4,5],[{1,2},{1,3,4},{2,2,4},{1,4,5},{2,3,5}]]),
00060   assert(f(6) = [[1,2,3,4,5,6],[{1,2},{1,3,4},{2,2,4},{1,4,5},{2,3,5},{1,5,6},{3,6}]]),
00061   true)\$
00062
00063 okltest_schurtriples_me_hg(f) := (
00064   for n : 0 thru if oklib_test_level=0 then 10 else 50 do
00065    block([G : schurtriples_hg(n)],
00066     assert(f(n) = [G[1], min_elements(G[2])])
00067   ),
00068   true)\$
00069
00070 okltest_wschurtriples_ohg(f) := (
00071   assert(f(0) = [[],[]]),
00072   assert(f(1) = [[1],[]]),
00073   assert(f(2) = [[1,2],[]]),
00074   assert(f(3) = [[1,2,3],[{1,2,3}]]),
00075   assert(f(4) = [[1,2,3,4],[{1,2,3},{1,3,4}]]),
00076   assert(f(5) = [[1,2,3,4,5],[{1,2,3},{1,3,4},{1,4,5},{2,3,5}]]),
00077   assert(f(6) = [[1,2,3,4,5,6],[{1,2,3},{1,3,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6}]]),
00078   assert(f(7) = [[1,2,3,4,5,6,7],[{1,2,3},{1,3,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6},{1,6,7},{2,5,7},{3,4,7}]]),
00079   assert(f(8) = [[1,2,3,4,5,6,7,8],[{1,2,3},{1,3,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6},{1,6,7},{2,5,7},{3,4,7},{1,7,8},{2,6,8},{3,5,8}]]),
00080   for n : 0 thru 15 do block([G : schurtriples_ohg(n)],
00081     assert(f(n) = [G[1], sublist(G[2], lambda([H], is(length(H)=3)))])
00082   ),
00083   true)\$
00084
00085 okltest_nhyp_list_schurtriples_ohg(f) := (
00086   for n : 0 thru 10 do
00087     assert(f(n) = nhyp_list_ohg(schurtriples_ohg(n))),
00088   true)\$
00089
00090 okltest_nhyp_list_schurtriples_me_ohg(f) := (
00091   for n : 0 thru 20 do
00092     assert(f(n) = nhyp_list_ohg(schurtriples_me_ohg(n))),
00093   true)\$
00094
00095 okltest_nhyp_list_wschurtriples_ohg(f) := (
00096   for n : 0 thru 10 do
00097     assert(f(n) = nhyp_list_ohg(wschurtriples_ohg(n))),
00098   true)\$
00099
00100 okltest_nhyp_schurtriples_ohg(f) := (
00101   for n : 0 thru 10 do
00102     assert(f(n) = nhyp_ohg(schurtriples_ohg(n))),
00103   true)\$
00104
00105 okltest_nhyp_schurtriples_me_ohg(f) := (
00106   for n : 0 thru 10 do
00107     assert(f(n) = nhyp_ohg(schurtriples_me_ohg(n))),
00108   true)\$
00109
00110 okltest_nhyp_wschurtriples_ohg(f) := (
00111   for n : 0 thru 10 do
00112     assert(f(n) = nhyp_ohg(wschurtriples_ohg(n))),
00113   true)\$
00114
00115 okltest_has_schurtriple(f) := (
00116   assert(f({}) = false),
00117   assert(f({0}) = true),
00118   assert(f({1}) = false),
00119   assert(f({1,2}) = true),
00120   assert(f({1,3}) = false),
00121   assert(f({2,3}) = false),
00122   assert(f({2,4}) = true),
00123   assert(f({1,2,3}) = true),
00124   assert(f({-1,2,3}) = true),
00125   assert(f({-1,2,4}) = true),
00126   assert(f({-1,2,5}) = false),
00127   assert(f({2,4,6,12}) = true),
00128   assert(f({2,4,7,12}) = true),
00129   assert(f({2,5,7,12}) = true),
00130   assert(f({2,6,7,12}) = true),
00131   assert(f({2,6,7,15}) = false),
00132   assert(f({4,5,15,16,22,28,29,39,40,41,42,48,49,59}) = false),
00133   assert(f({1,4,7,10,30}) = false),
00134   assert(f({1,4,7,10,30,37}) = true),
00135   true)\$
00136
00137 okltest_has_wschurtriple(f) := (
00138   assert(f({}) = false),
00139   assert(f({0}) = false),
00140   assert(f({1}) = false),
00141   assert(f({1,2}) = false),
00142   assert(f({1,3}) = false),
00143   assert(f({2,3}) = false),
00144   assert(f({2,4}) = false),
00145   assert(f({1,2,3}) = true),
00146   assert(f({-1,2,3}) = true),
00147   assert(f({-1,2,4}) = false),
00148   assert(f({-1,2,5}) = false),
00149   assert(f({2,4,6,12}) = true),
00150   assert(f({2,4,7,12}) = false),
00151   assert(f({2,5,7,12}) = true),
00152   assert(f({2,6,7,12}) = false),
00153   assert(f({2,6,7,15}) = false),
00154   assert(f({4,5,15,16,22,28,29,39,40,41,42,48,49,59}) = false),
00155   assert(f({1,4,7,10,30}) = false),
00156   assert(f({1,4,7,10,30,37}) = true),
00157   true)\$
00158
00159
00160 /* ************
00161    * Symmetry *
00162    ************
00163 */
00164
00165 okltest_schurtriples_pd_ohg(f) := (
00166   assert(f(0) = [[],[]]),
00167   assert(f(1) = [[1],[]]),
00168   assert(f(2) = [[1,2],[{1,2}]]),
00169   assert(f(3) = [[1,2],[{1,2}]]),
00170   assert(f(4) = [[1,2],[{1,2}]]),
00171   assert(f(5) = [[1,2,3,4],[{1,2},{1,4},{2,4}]]),
00172   assert(f(6) = [[1,2,3],[{1,2},{1,3},{2,3}]]),
00173   assert(f(7) = [[1,2,3,4],[{1,2},{2,3},{2,4},{1,3,4}]]),
00174   assert(f(8) = [[1,2,3,4,6],[{1,2},{1,4},{2,4},{3,6}]]),
00175   true)\$
00176
00177 okltest_wschurtriples_pd_ohg(f) := (
00178   assert(f(0) = [[],[]]),
00179   assert(f(1) = [[1],[]]),
00180   assert(f(2) = [[1],[]]),
00181   assert(f(3) = [[1,2],[{1,2}]]),
00182   assert(f(4) = [[1,2],[{1,2}]]),
00183   assert(f(5) = [[1,2,3],[{1,2}]]),
00184   assert(f(6) = [[1,2,3],[{1,2},{1,3},{2,3}]]),
00185   assert(f(7) = [[1,2,3,4],[{1,2},{2,3},{2,4},{1,3,4}]]),
00186   assert(f(8) = [[1,2,3,4],[{1,2},{1,4},{2,4}]]),
00187   true)\$
00188
00189 okltest_nver_schurtriples_pd_ohg(f) := (
00190   for n : 0 thru cokltl(10,20) do
00191     assert(f(n) = nver_ohg(schurtriples_pd_ohg(n))),
00192   true)\$
00193
00194 okltest_nver_wschurtriples_pd_ohg(f) := (
00195   for n : 0 thru cokltl(10,20) do
00196     assert(f(n) = nver_ohg(wschurtriples_pd_ohg(n))),
00197   true)\$
00198
00199
00200 /* *****************
00201    * Group triples *
00202    *****************
00203 */
00204
00205 okltest_grouptriples_ougrp2ohg(f) := (
00206   assert(f(cyclic_ougrp(1)) = [[],[]]),
00207   /* XXX */
00208   true)\$
00209
00210 okltest_grouptriples_ugrp2hg(f) := (
00211   assert(f(cyclic_ugrp(1)) = [{},{}]),
00212   /* XXX */
00213   true)\$
00214
00215 okltest_grouptriples_me_ougrp2ohg(f) := (
00216   assert(f(cyclic_ougrp(1)) = [[],[]]),
00217   /* XXX */
00218   true)\$
00219
00220 okltest_grouptriples_me_ugrp2hg(f) := (
00221   assert(f(cyclic_ugrp(1)) = [{},{}]),
00222   /* XXX */
00223   true)\$
00224
00225 okltest_wgrouptriples_ougrp2ohg(f) := (
00226   assert(f(cyclic_ougrp(1)) = [[],[]]),
00227   /* XXX */
00228   true)\$
00229
00230 okltest_wgrouptriples_ugrp2hg(f) := (
00231   assert(f(cyclic_ugrp(1)) = [{},{}]),
00232   /* XXX */
00233   true)\$
00234
00235 okltest_nver_grouptriples_ougrp2ohg(f) := block([C],
00236   assert(f([[0],C]) = 0),
00237   assert(f([[0,1],C]) = 1),
00238   assert(f([[0,1,3],C]) = 2),
00239   true)\$
00240
00241 okltest_nver_grouptriples_ugrp2hg(f) := block([C],
00242   assert(f([{0},C]) = 0),
00243   assert(f([{0,1},C]) = 1),
00244   assert(f([{0,1,3},C]) = 2),
00245   true)\$
00246
00247 okltest_nver_grouptriples_me_ougrp2ohg(f) := block([C],
00248   assert(f([[0],C]) = 0),
00249   assert(f([[0,1],C]) = 1),
00250   assert(f([[0,1,3],C]) = 2),
00251   true)\$
00252
00253 okltest_nver_grouptriples_me_ugrp2hg(f) := block([C],
00254   assert(f([{0},C]) = 0),
00255   assert(f([{0,1},C]) = 1),
00256   assert(f([{0,1,3},C]) = 2),
00257   true)\$
00258
00259 okltest_nver_wgrouptriples_ougrp2ohg(f) := block([C],
00260   assert(f([[0],C]) = 0),
00261   assert(f([[0,1],C]) = 1),
00262   assert(f([[0,1,3],C]) = 2),
00263   true)\$
00264
00265 okltest_nver_wgrouptriples_ugrp2hg(f) := block([C],
00266   assert(f([{0},C]) = 0),
00267   assert(f([{0,1},C]) = 1),
00268   assert(f([{0,1,3},C]) = 2),
00269   true)\$
00270
00271 okltest_nhyp_grouptriples_ougrp2ohg(f) := (
00272   for G in append(create_list(cyclic_ougrp(n),n,1,cokltl(5,20)), create_list(sym_l_ougrp(n),n,1,cokltl(4,5))) do
00273     assert(f(G) = nhyp_ohg(grouptriples_ougrp2ohg(G))),
00274   true)\$
00275
00276 okltest_nhyp_wgrouptriples_ougrp2ohg(f) := (
00277   for G in append(create_list(cyclic_ougrp(n),n,1,cokltl(5,20)), create_list(sym_l_ougrp(n),n,1,cokltl(4,5))) do
00278     assert(f(G) = nhyp_ohg(wgrouptriples_ougrp2ohg(G))),
00279   true)\$
00280
00281 okltest_mschurtriples_ohg(f) := (
00282   assert(f(0) = [[],[]]),
00283   assert(f(1) = [[1],[]]),
00284   assert(f(2) = [[1,2],[{1,2},{1,2}]]),
00285   assert(f(3) = [[1,2,3],[{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3}]]),
00286   assert(f(4) = [[1,2,3,4],[{1,2},{1,2,3},{1,3,4},{1,2,3},{2,4},{1,2,4},{1,3,4},{1,3},{2,3,4},{1,2,4},{2,3,4},{3,4}]]),
00287   true)\$
00288
00289 okltest_mschurtriples_hg(f) := (
00290   assert(f(0) = [{},{}]),
00291   assert(f(1) = [{1},{}]),
00292   assert(f(2) = [{1,2},{{1,2}}]),
00293   assert(f(3) = [{1,2,3},{{1,2},{1,2,3},{2,3}}]),
00294   assert(f(4) = [{1,2,3,4},{{1,2},{1,2,3},{1,3,4},{2,4},{1,2,4},{1,3},{2,3,4},{1,2,4},{3,4}}]),
00295   true)\$
00296
00297 okltest_mschurtriples_me_ohg(f) := (
00298   assert(f(0) = [[],[]]),
00299   assert(f(1) = [[1],[]]),
00300   assert(f(2) = [[1,2],[{1,2}]]),
00301   assert(f(3) = [[1,2,3],[{1,2},{2,3}]]),
00302   assert(f(4) = [[1,2,3,4],[{1,2},{2,4},{1,3},{3,4}]]),
00303   true)\$
00304
00305 okltest_mschurtriples_me_hg(f) := (
00306   assert(f(0) = [{},{}]),
00307   assert(f(1) = [{1},{}]),
00308   assert(f(2) = [{1,2},{{1,2}}]),
00309   assert(f(3) = [{1,2,3},{{1,2},{2,3}}]),
00310   assert(f(4) = [{1,2,3,4},{{1,2},{2,4},{1,3},{3,4}}]),
00311   true)\$
00312
00313 okltest_wmschurtriples_ohg(f) := (
00314   assert(f(0) = [[],[]]),
00315   assert(f(1) = [[1],[]]),
00316   assert(f(2) = [[1,2],[]]),
00317   assert(f(3) = [[1,2,3],[{1,2,3},{1,2,3},{1,2,3},{1,2,3}]]),
00318   assert(f(4) = [[1,2,3,4],[{1,2,3},{1,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,4},{2,3,4}]]),
00319   true)\$
00320
00321 okltest_wmschurtriples_hg(f) := (
00322   assert(f(0) = [{},{}]),
00323   assert(f(1) = [{1},{}]),
00324   assert(f(2) = [{1,2},{}]),
00325   assert(f(3) = [{1,2,3},{{1,2,3}}]),
00326   assert(f(4) = [{1,2,3,4},{{1,2,3},{1,3,4},{1,2,4},{2,3,4},{1,2,4}}]),
00327   true)\$
00328
00329 okltest_nver_mschurtriples_ohg(f) := (
00330   for n : 0 thru cokltl(10,20) do
00331     assert(f(n) = nver_ohg(mschurtriples_ohg(n))),
00332   true)\$
00333
00334 okltest_nver_mschurtriples_hg(f) := (
00335   for n : 0 thru cokltl(10,20) do
00336     assert(f(n) = nver_hg(mschurtriples_hg(n))),
00337   true)\$
00338
00339 okltest_nver_mschurtriples_me_ohg(f) := (
00340   for n : 0 thru cokltl(10,20) do
00341     assert(f(n) = nver_ohg(mschurtriples_me_ohg(n))),
00342   true)\$
00343
00344 okltest_nver_mschurtriples_me_hg(f) := (
00345   for n : 0 thru cokltl(10,20) do
00346     assert(f(n) = nver_hg(mschurtriples_me_hg(n))),
00347   true)\$
00348
00349 okltest_nver_wmschurtriples_ohg(f) := (
00350   for n : 0 thru cokltl(10,20) do
00351     assert(f(n) = nver_ohg(wmschurtriples_ohg(n))),
00352   true)\$
00353
00354 okltest_nver_wmschurtriples_hg(f) := (
00355   for n : 0 thru cokltl(10,20) do
00356     assert(f(n) = nver_hg(wmschurtriples_hg(n))),
00357   true)\$
00358
00359 okltest_nhyp_mschurtriples_ohg(f) := (
00360   for n : 0 thru cokltl(10,20) do
00361     assert(f(n) = nhyp_ohg(mschurtriples_ohg(n))),
00362   true)\$
00363
00364 /*
00365 okltest_nhyp_mschurtriples_hg(f) := (
00366   for n : 0 thru cokltl(10,20) do
00367     assert(f(n) = nhyp_hg(mschurtriples_hg(n))),
00368   true)\$
00369 */
00370
00371 /*
00372 okltest_nhyp_mschurtriples_me_ohg(f) := (
00373   for n : 0 thru cokltl(10,20) do
00374     assert(f(n) = nhyp_ohg(mschurtriples_me_ohg(n))),
00375   true)\$
00376 */
00377
00378 /*
00379 okltest_nhyp_mschurtriples_me_hg(f) := (
00380   for n : 0 thru cokltl(10,20) do
00381     assert(f(n) = nhyp_hg(mschurtriples_me_hg(n))),
00382   true)\$
00383 */
00384
00385 okltest_nhyp_wmschurtriples_ohg(f) := (
00386   for n : 0 thru cokltl(10,20) do
00387     assert(f(n) = nhyp_ohg(wmschurtriples_ohg(n))),
00388   true)\$
00389
00390 /*
00391 okltest_nhyp_wmschurtriples_hg(f) := (
00392   for n : 0 thru cokltl(10,20) do
00393     assert(f(n) = nhyp_ohg(wmschurtriples_hg(n))),
00394   true)\$
00395 */
00396
00397 okltest_symmetrictriples_ohg(f) := (
00398   assert(f(0) = [[],[]]),
00399   assert(f(1) = [[],[]]),
00400   assert(f(2) = [[[2,1]],[]]),
00401   assert(f(3)[1] = [[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
00402   /* XXX */
00403   true)\$
00404
00405 okltest_symmetrictriples_hg(f) := (
00406   assert(f(0) = [{},{}]),
00407   assert(f(1) = [{},{}]),
00408   assert(f(2) = [{[2,1]},{}]),
00409   assert(f(3)[1] = {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}),
00410   /* XXX */
00411   true)\$
00412
00413 okltest_symmetrictriples_me_ohg(f) := (
00414   assert(f(0) = [[],[]]),
00415   assert(f(1) = [[],[]]),
00416   assert(f(2) = [[[2,1]],[]]),
00417   assert(f(3)[1] = [[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
00418   /* XXX */
00419   true)\$
00420
00421 okltest_symmetrictriples_me_hg(f) := (
00422   assert(f(0) = [{},{}]),
00423   assert(f(1) = [{},{}]),
00424   assert(f(2) = [{[2,1]},{}]),
00425   assert(f(3)[1] = {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}),
00426   /* XXX */
00427   true)\$
00428
00429 okltest_wsymmetrictriples_ohg(f) := (
00430   assert(f(0) = [[],[]]),
00431   assert(f(1) = [[],[]]),
00432   assert(f(2) = [[[2,1]],[]]),
00433   assert(f(3)[1] = [[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
00434   /* XXX */
00435   true)\$
00436
00437 okltest_wsymmetrictriples_hg(f) := (
00438   assert(f(0) = [{},{}]),
00439   assert(f(1) = [{},{}]),
00440   assert(f(2) = [{[2,1]},{}]),
00441   assert(f(3)[1] = {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}),
00442   /* XXX */
00443   true)\$
00444
00445 okltest_nver_symmetrictriples_ohg(f) := (
00446   for n : 0 thru cokltl(3,4,5) do
00447     assert(f(n) = nver_ohg(symmetrictriples_ohg(n))),
00448   true)\$
00449
00450 okltest_nver_symmetrictriples_hg(f) := (
00451   for n : 0 thru cokltl(3,4,5) do
00452     assert(f(n) = nver_hg(symmetrictriples_hg(n))),
00453   true)\$
00454
00455 okltest_nver_symmetrictriples_me_ohg(f) := (
00456   for n : 0 thru cokltl(3,4,5) do
00457     assert(f(n) = nver_ohg(symmetrictriples_me_ohg(n))),
00458   true)\$
00459
00460 okltest_nver_symmetrictriples_me_hg(f) := (
00461   for n : 0 thru cokltl(3,4,5) do
00462     assert(f(n) = nver_hg(symmetrictriples_me_hg(n))),
00463   true)\$
00464
00465 okltest_nver_wsymmetrictriples_ohg(f) := (
00466   for n : 0 thru cokltl(3,4,5) do
00467     assert(f(n) = nver_ohg(wsymmetrictriples_ohg(n))),
00468   true)\$
00469
00470 okltest_nver_wsymmetrictriples_hg(f) := (
00471   for n : 0 thru cokltl(3,4,5) do
00472     assert(f(n) = nver_hg(wsymmetrictriples_hg(n))),
00473   true)\$
00474
00475 okltest_nhyp_symmetrictriples_ohg(f) := (
00476   for n : 0 thru cokltl(3,4,5) do
00477     assert(f(n) = nhyp_ohg(symmetrictriples_ohg(n))),
00478   true)\$
00479
00480 okltest_nhyp_wsymmetrictriples_ohg(f) := (
00481   for n : 0 thru cokltl(3,4,5) do
00482     assert(f(n) = nhyp_ohg(wsymmetrictriples_ohg(n))),
00483   true)\$
00484
00485
```