OKlibrary  0.2.1.6
Enumeration.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 14.1.2009 (Swansea) */
00002 /* Copyright 2009 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
00025 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/BasicNotions.mac")\$
00026 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Homomorphisms.mac")\$
00027 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")\$
00028 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")\$
00029 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/Auxiliary.mac")\$
00030 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")\$
00031
00032
00033 /* *********************
00034    * Basic enumeration *
00035    *********************
00036 */
00037
00038 /* All groupoids of order n, as Maxima matrices: */
00039 all_grd2m(n) := all_m(n,n,create_list(i,i,1,n))\$
00040 all_grd(n) := map(m2grd,all_grd2m(n))\$
00041
00042
00043 /* ************
00044    * Counting *
00045    ************
00046 */
00047
00048 number_grd(n) := pow(n, n^2)\$
00049 number_iso_grd(n) := if n<=1 then 1 elseif n=2 then 10 elseif n=3 then 3330
00050   else unknown\$
00051 number_isot_grd(n) := if n<=1 then 1 elseif n=2 then 5 elseif n=3 then 139
00052   else unknown\$
00053
00054 /* Commutativity: */
00055 number_cgrd(n) := pow(n, n*(n+1)/2)\$
00056 number_iso_cgrd(n) := if n<=1 then 1 elseif n=2 then 4 elseif n=3 then 129
00057   else unknown\$
00058
00059 /* Unit element: */
00060 number_ugrd(n) := n * n^((n-1)^2)\$
00061 number_iso_ugrd(n) := if n<=1 then n elseif n=2 then 2 elseif n=3 then 45
00062   else unknown\$
00063
00064 number_cugrd(n) := n * pow(n, n*(n-1)/2)\$
00065 number_iso_cugrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 15
00066   else unknown\$
00067
00068 /* Idempotent: */
00069 number_igrd(n) := pow(n, n^2-n)\$
00070 number_iso_igrd(n) := if n<=1 then 1 elseif n=2 then 3 elseif n=3 then 138
00071   else unknown\$
00072
00073 number_iugrd(n) := n * n^((n-1)^2 - (n-1))\$
00074 number_iso_iugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 6
00075   else unknown\$
00076
00077 number_cigrd(n) := pow(n, n*(n-1)/2)\$
00078 number_iso_cigrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 7
00079   else unknown\$
00080
00081 number_ciugrd(n) := pow(n, n*(n+1)/2-2*n+2)\$
00082 number_iso_ciugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 2
00083   else unknown\$
00084
00085 /* Null element: */
00086 number_ngrd(n) := n * n^((n-1)^2)\$
00087 number_iso_ngrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 45
00088   else unknown\$
00089
00090 number_cngrd(n) := n * pow(n,n*(n-1)/2)\$
00091 number_iso_cngrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 15
00092   else unknown\$
00093
00094 number_ingrd(n) := n * n^((n-1)*(n-2))\$
00095 number_iso_ingrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 6
00096   else unknown\$
00097
00098 number_nugrd(n) := if n <= 1 then n else n*(n-1)*n^((n-2)^2)\$
00099 number_iso_nugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 3
00100   else unknown\$
00101
00102 number_cingrd(n) := n^(n*(n+1)/2-2*n+2)\$
00103 number_iso_cingrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 2
00104   else unknown\$
00105
00106 number_cnugrd(n) := if n<=1 then n else n*(n-1)*n^((n-1)*(n-2)/2)\$
00107 number_iso_cnugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 3
00108   else unknown\$
00109
00110 number_inugrd(n) := if n <= 1 then n else n*(n-1)*n^((n-2)*(n-3))\$
00111 number_iso_inugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 1
00112   else unknown\$
00113
00114 number_cinugrd(n) := if n<=1 then n else n*(n-1)*n^((n-2)*(n-3)/2)\$
00115 number_iso_cinugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 1
00116   else unknown\$
00117
00118
00119 /* ***********************************
00120    * Enumerating isomorphism classes *
00121    ***********************************
00122 */
00123
00124 /* The isomorphism classes of the set of all standardised groupoids of order n
00125    (with base set {1,...,n}); the results are directly represented as
00126    Maxima matrices. (Given such a matrix M, the corresponding groupoid
00127    is obtained by scom2grd(m2scom(M)).)
00128 */
00129 /* First the direct computation: */
00130 all_isomorphism_classes_bydef_grd(n) :=
00131  map(lambda([C], map(lambda([G], lmscom2m(grd2scom(G))), C)),
00132   equiv_classes(
00133     setify(all_grd(n)),
00134     is_isomorphic_bydef_grd))\$
00135 /* Now the more efficient computation by actively computing the
00136    equivalence classes.
00137 */
00138 /* First an auxiliary function, which for a given set S of groupoids
00139    represented as Maxima matrices computes the complete isomorphism
00140    classes of these matrices (w.r.t. all groupoids of order n).
00141    Inherits: the set all_perm of permutations of N
00142    (as functions).
00143 */
00144 all_isomorphism_classes_actively_sm_grd(S) := block(
00145  [result : []],
00146   while not emptyp(S) do block(
00147    [M : m2grd(choose_element(S)), C],
00148     /* C is the isomorphism class of M */
00149     C : setify(map(lambda([f], grd2m(transport_grd(M,f))), all_perm)),
00150     S : setdifference(S, C),
00151     result : cons(C,result)
00152   ),
00153   setify(result))\$
00154 /* Now the full function (running through all groupoids of order n):
00155 */
00156 all_isomorphism_classes_actively_grd(n) := block(
00157  [N : create_list(i,i,1,n), all_perm],
00158   all_perm : map(lambda([p], lambda_array(l2ary(p))),
00159            listify(permutations(N))), /* all permutations */
00160   all_isomorphism_classes_actively_sm_grd(setify(all_m(n,n,N))))\$
00161
00162
00163 /* *********************************
00164    * Enumerating isotopism classes *
00165    *********************************
00166 */
00167
00168 /* Now all isotopy classes (a rougher equivalence relation than isomorphism):
00169 */
00170 /* Perhaps should be better also organised as above. XXX */
00171 all_isotopism_classes_actively_grd(n) := block(
00172  [N : create_list(i,i,1,n), G, LP, LP3, result : []],
00173   G : setify(all_m(n,n,N)), /* all groupoids */
00174   LP : map(lambda([p], lambda_array(l2ary(p))),
00175            listify(permutations(N))), /* all permutations */
00176   LP3 : cartesian_product_l([LP,LP,LP]),
00177   while not emptyp(G) do block(
00178    [M : m2grd(choose_element(G)), C],
00179     /* C is the isomorphism class of M */
00180     C : setify(map(lambda([F],
00181                  grd2m(transport3_grd(M,F[1],F[2],F[3]))), LP3)),
00182     G : setdifference(G, C),
00183     result : cons(C,result)
00184   ),
00185   setify(result))\$
00186
00187 /* Creating all isotopy classes, which are further subdivided into
00188    isomorphism classes:
00189 */
00190 all_isotopismisomorphism_classes_actively_grd(n) := block(
00191  [all_perm : map(lambda([p], lambda_array(l2ary(p))),
00192            listify(permutations(create_list(i,i,1,n))))],
00193   map(all_isomorphism_classes_actively_sm_grd,
00194       all_isotopism_classes_actively_grd(n)))\$
00195
00196
00197 /* ********************
00198    * Evaluation tools *
00199    ********************
00200 */
00201
00202 /* Given a set S of isomorphism classes of Maxima-matrices representing
00203    groupoids, select those classes fulfilling all the properties of the
00204    list P:
00205 */
00206 selectclasses_m2grd(S,P) := subset(S, lambda([C],
00207   block([M : m2grd(first_element(C))],
00208     every_s(lambda([p], p(M)), P))))\$
00209
```